20pts求助!新年快乐!
查看原帖
20pts求助!新年快乐!
933808
Earth2023楼主2024/12/31 22:11
#include <iostream>
#include <queue>
using namespace std;
struct node {
	int x, y, how90, fx;
};
int n;
char map[105][105];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
bool vis[105][105];
queue<node> Q;
void bfs(int stX, int stY, int edX, int edY) {
	for (int i = 0; i < 4; i++) {
		int nx = stX + dx[i], ny = stY + dy[i];
		if (map[nx][ny] == 'B') {
			cout << 0 << endl;
			return;
		}
		if (map[nx][ny] == '.') {
			Q.push({nx, ny, 0, i});
		}
	}
	while (!Q.empty()) {
		node p = Q.front();
		Q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = p.x + dx[i], ny = p.y + dy[i];
			if (nx < 1 || nx > n || ny < 1 || ny > n || vis[nx][ny]) continue;
			if (map[nx][ny] == '.') {
				if (i != p.fx) Q.push({nx, ny, p.how90 + 1, i});
				else Q.push({nx, ny, p.how90, p.fx});
				vis[nx][ny] = 1;
			} else if (map[nx][ny] == 'B') {
				if (i != p.fx) cout << p.how90 + 1 << endl;
				else cout << p.how90 << endl;
				return;
			}
		}
	}
}
int main() {
	cin >> n;
	int bx, by, ex, ey;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'A') bx = i, by = j;
			else if (map[i][j] == 'B') ex = i, ey = j; 
		}
	}
	bfs(bx, by, ex, ey);
	return 0;
}
2024/12/31 22:11
加载中...