6 分求助
查看原帖
6 分求助
448887
cancan123456楼主2023/8/4 21:59
#include <cstdio>
#include <queue>
using namespace std;
char s[505][505];
struct Point {
	int x, y;
	Point(int a, int b) {
		x = a;
		y = b;
	}
};
int n, m, dis[505][505], dx[4] = {-1, 1, -1, 1}, dy[4] = {-1, -1, 1, 1};
bool vis[505][505];
bool in_range(int x, int y) {
	return 0 <= x && x <= n && 0 <= y && y <= m;
}
int val(int i, int j, int p) {
	if (p == 0) {
		return s[i - 1][j - 1] == '\\' ? 0 : 1;
	} else if (p == 1) {
		return s[i - 1][j] == '/' ? 0 : 1;
	} else if (p == 2) {
		return s[i][j - 1] == '/' ? 0 : 1;
	} else {
		return s[i][j] == '\\' ? 0 : 1;
	}
}
int solve() {
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			vis[i][j] = false;
		}
	}
	deque < Point > q;
	q.push_back(Point(0, 0));
	vis[0][0] = true;
	while (!q.empty()) {
		Point f = q.front();
		q.pop_front();
		int x = f.x, y = f.y;
		for (int i = 0; i < 4; i++) {
			if (in_range(x + dx[i], y + dy[i]) && !vis[x + dx[i]][y + dy[i]]) {
				vis[x + dx[i]][y + dy[i]] = true;
				if (val(x, y, i) == 0) {
					dis[x + dx[i]][y + dy[i]] = dis[x][y];
					q.push_front(Point(x + dx[i], y + dy[i]));
				} else {
					dis[x + dx[i]][y + dy[i]] = dis[x][y] + 1;
					q.push_back(Point(x + dx[i], y + dy[i]));
				}
			}
		}
	}
	return dis[n][m];
}
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%s", s[i]);
	}
	if ((n + m) % 2 == 1) {
		printf("NO SOLUTION\n");
	} else {
		printf("%d\n", solve());
	}
	return 0;
}
2023/8/4 21:59
加载中...