70pts求调
查看原帖
70pts求调
489257
Mirage_Insane楼主2022/3/25 18:04
#include<bits/stdc++.h>
using namespace std;
#define SF scanf
#define PF printf
int d1[5] = {0, 0, 1, -1}, d2[5] = {1, -1, 0, 0}, d3[15] = {0, 0, 1, -1, -1, -1, 1, 1}, d4[15] = {1, -1, 0, 0, -1, 1, -1, 1}, a, b, a1, b1, n, m, ans;
bool vis[1055][1055], as;
char mp[1055][1055];
struct node {
	int x, y, s;
};
bool check(int x, int y) {
	for(int i = 0; i < 8; i++) {
		int nx = x, ny = y;
		while(1) {
			if(nx < 1 || ny < 1 || nx > n || ny > m) break;
			if(mp[nx][ny] == 'X') break;
			if(nx == a1 && ny == b1) return true;
			nx += d3[i];
			ny += d4[i];
		}
	}
	return false;
}
queue<node> q;
void bfs(int x, int y) {
	memset(vis, 0, sizeof(vis));
	while(!q.empty()) q.pop();
	q.push((node){x, y, 0});
	while(!q.empty()) {
		node tmp = q.front();
		q.pop();
		for(int i = 0; i < 4; i++) {
			int nx = tmp.x + d1[i];
			int ny = tmp.y + d2[i];
			if(nx < 1 || ny < 1 || nx > n || ny > m) continue;
			if(vis[nx][ny] || mp[nx][ny] == 'X') continue;
			if(check(nx, ny)) {
				as = 1;
				PF("%d\n", tmp.s + 1);
				return;
			}
			vis[nx][ny] = 1;
			q.push((node){nx, ny, tmp.s + 1});
		}
	}
}
int main() {
	SF("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> mp[i][j];
		}
	}
	while(SF("%d%d%d%d", &a1, &b1, &a, &b) != EOF) {
		if(a1 == 0 && b1 == 0 && a == 0 && b == 0) break;
		if(a == a1 && b == b1) {
			PF("0\n");
			continue;
		}
		as = 0;
		bfs(a, b);
		if(!as) {
			PF("Poor Harry\n");
		}
	}
	return 0;
} 

2022/3/25 18:04
加载中...