BFS 8分求调
查看原帖
BFS 8分求调
1030381
AFO_Lzx楼主2024/10/25 13:18
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e2 + 5;
int n, m, sx, sy, ex, ey;
char a[N][N];
bool vis[N][N];

const int fx[] = {0, 0, 1, 0, -1, -1, -1, 1, 1};
const int fy[] = {0, 1, 0, -1, 0, -1, 1, -1, 1};

struct node {
	int x, y;
	int step;
};

int bfs() {
	queue<node> q;
	q.push({sx, sy, 0});
	vis[sx][sy] = 1;
	
	while (q.empty() == 0) {
		node u = q.front(); q.pop();
		for (int i = 1; i <= 8; i++) {
			int tx = u.x + fx[i];
			int ty = u.y + fy[i];
			
			if (tx <= 0 || tx > n || ty <= 0 || ty > m) continue;
			if (a[tx][ty] == 'X' || vis[tx][ty] == 1) continue;
			if (tx == ex && ty == ey) return u.step + 1;
			
			vis[tx][ty] = 1;
			q.push({tx, ty, u.step + 1});
		}
	} 
	
	return -1;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	
	while (cin >> ex >> ey >> sx >> sy) {
		if (sx == 0 && sy == 0 && ex == 0 && ey == 0) return 0;
		for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) vis[i][j] = 0;
		int ans = bfs();
		
		if (ans == -1) cout << "Poor Harry\n";
		else cout << ans << "\n";
	}
	
	return 0;
}
2024/10/25 13:18
加载中...