20分求助!!!
查看原帖
20分求助!!!
525056
I_love_LPN_Forever楼主2022/3/26 16:49
#include <bits/stdc++.h>
#define maxn 1005
using namespace std;
int d1[5] = {0, 0, 1, -1}, d2[5] = {1, -1, 0, 0};
int d3[15] = {0, 0, 1, -1, -1, -1, 1, 1}, d4[15] = {1, -1, 0, 0, -1, 1, -1, 1};
int sx, sy, ex, ey;
int n, m, fl, mp[maxn][maxn], vis[maxn][maxn];
struct node {
	int x, y, s;
} p;
bool check(int x, int y) {
	for (int i = 0; i < 8; i++) {
		int nx = x, ny = y;
		while (1) {
			if (nx < 1 || nx > n || ny < 1 || ny > m)
				break;
			if (nx == ex && ny == ey)
				return true;
			if (mp[nx][ny])
				break;
			nx += d3[i], ny += d4[i];
		}
	}
	return false;
}
void bfs(int x, int y) {
	queue<node> q;
	p.x = x, p.y = y, p.s = 0;
	q.push(p);
	while (q.size()) {
		p = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = p.x + d1[i], ny = p.y + d2[i], ns = p.s + 1;
			if (nx > 0 && nx <= n && ny > 0 && ny <= m && !mp[nx][ny] && !vis[nx][ny]) {
				vis[nx][ny] = 1;
				if (check(nx, ny)) {
					cout << ns << endl;
					fl = 1;
					break;
				}
				q.push(node {nx, ny, ns});
			}
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char x;
			cin >> x;
			if (x == 'X')
				mp[i][j] = 1;
		}
	}
	while (1) {
		memset(vis, 0, sizeof(vis));
		scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
		fl = 0;
		if (check(sx, sy)) {
			cout << 0 << endl;
			continue;
		}
		if (!sx && !sy && !ex && !ey) {
			return 0;
		}
		bfs(sx, sy);
		if (!fl)
			puts("Poor Harry");
	}
	return 0;
}
2022/3/26 16:49
加载中...