36测试点出错,求大佬看看哪里出错了
查看原帖
36测试点出错,求大佬看看哪里出错了
971468
a13570081961楼主2024/7/26 22:28
// 刷题.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include<deque>
using namespace std;
int n, m;//n行,m列
bool route[1000000];
deque<int>q;
int dis[4][2] = { {-1,-1},{-1,1},{1,1},{1,-1} };
int dis1[4][2] = { {-1,-1},{-1,0},{0,0},{0,-1} };
int d[1000000];
int po(int l, int r) {
	return (l - 1) * (m+1) + r;
}
bool vis[1000000] = { 0 };
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	if (n % 2 != m % 2) {
		cout << "NO SOLUTION";
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char a;
			cin >> a;
			if (a == '/')
				route[po(i,j)] = 0;
			else
				route[po(i,j)] = 1;
		}
	}
	q.push_front(1);
	d[1] = 0;
	vis[1] = 1;
	while (!q.empty()) {
		int l = q.front() / (m+1) + 1;
		int r = q.front() % (m+1);
		q.pop_front();
		for (int i = 0; i < 4; i++) {
			int nl = l + dis[i][0];
			int nr = r + dis[i][1];
			if (nl <= 0 || nl > n+1)continue;
			if (nr <= 0 || nr > m+1)continue;
			
			int rl = l + dis1[i][0];
			int rr = r + dis1[i][1];
			
			if (route[po(rl, rr)]) {
				if (i == 0 || i == 2) {
					if (vis[po(nl, nr)]) {
						if (d[po(nl, nr)] <= d[po(l, r)])continue;
					}
					d[po(nl, nr)] = d[po(l, r)];
					q.push_front(po(nl, nr));
				}
				else {
					if (vis[po(nl, nr)]) {
						if (d[po(nl, nr)] <= d[po(l, r)]+1)continue;
					}
					d[po(nl, nr)] = d[po(l, r)]+1;
					q.push_back(po(nl, nr));
				}
			}
			else {
				if (i == 1 || i == 3) {
					if (vis[po(nl, nr)]) {
						if (d[po(nl, nr)] <= d[po(l, r)])continue;
					}
					d[po(nl, nr)] = d[po(l, r)];
					q.push_front(po(nl, nr));
				}
				else {
					if (vis[po(nl, nr)]) {
						if (d[po(nl, nr)] <= d[po(l, r)]+1)continue;
					}
					d[po(nl, nr)] = d[po(l, r)] + 1;
					q.push_back(po(nl, nr));
				}
			}
			vis[po(nl, nr)] = 1;
			
		}
	}

		cout << d[po(n+1, m+1)];
	return 0;
}
2024/7/26 22:28
加载中...