前十一个测试点wa最后一个re
#include <bits/stdc++.h>
using namespace std;
int bfs[16388][3],min,dir[5][2] = {{0,0},{0,-1},{1,0},{0,1},{-1,0}};
char a[2000][2000],b[2000][2000]; //b数组中,0表示障碍,1表示可通行,2表示终点,3表示已遍历过的部分
int main() {
////////////////////////////////////////信息输入
int n,m,hx[515],hy[515],medalx[515],medaly[515];
scanf("%d%d", &n,&m);
getchar();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) b[i][j] = '1';
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m;j++) {
scanf("%c", &a[i][j]);
if(a[i][j] == 'X') b[i][j] = '0';
}
getchar();
}
int coun=0;
for(int i = 1; i <= 512; i++) {
int t1,t2,t3,t4;
scanf("%d%d%d%d", &t1,&t2,&t3,&t4);
if(t1==0&&t2==0&&t3==0&&t4==0) {
coun = i-1;
break;
}
else {
hx[i] = t4; hy[i] = t3; medalx[i] = t2; medaly[i] = t1;
}
}
/////////////////////////////////////////////////
for(int i = 1; i <= coun; i++) {
b[medaly[i]][medalx[i]] = '2';
if(hx[i] == medalx[i] && hy[i] == medaly[i]) {
printf("0");continue;
}
// for(int j = 1; j <= m; j++) if(b[medaly[i]][j]!='0') b[medaly[i]][j] = '2';
// for(int j = 1; j <= n; j++) if(b[j][medalx[i]]!='0') b[j][medalx[i]] = '2';
//int tx=medalx[i],ty=medaly[i];
int pd[9] = {1,1,1,1,1,1,1,1,1}; //坐标1-8表示上下左右,下右,下左,上左,上右是否碰到障碍物的标志
//将可以看到奖杯的坐标标记
for(int j = 1; j <= max(n,m); j++) {
if(medaly[i]-j>=1 && b[medaly[i]-j][medalx[i]]!='0' && pd[1] != 0) b[medaly[i]-j][medalx[i]] = '2';
else pd[1] = 0;
if(medaly[i]+j<=n && b[medaly[i]+j][medalx[i]]!='0' && pd[2] != 0) b[medaly[i]+j][medalx[i]] = '2';
else pd[2] = 0;
if(medalx[i]-j>=1 && b[medaly[i]][medalx[i]-j]!='0' && pd[3] != 0) b[medaly[i]][medalx[i]-j] = '2';
else pd[3] = 0;
if(medalx[i]+j<=m && b[medaly[i]][medalx[i]+j]!='0' && pd[4] != 0) b[medaly[i]][medalx[i]+j] = '2';
else pd[4] = 0;
if(medalx[i]+j<=m && medaly[i]+j<=n && b[medaly[i]+j][medalx[i]+j] != '0' && pd[5] != 0) b[medaly[i]+j][medalx[i]+j] = '2';
else pd[5] = 0;
if(medalx[i]-j>=1 && medaly[i]+j<=n && b[medaly[i]+j][medalx[i]-j] != '0' && pd[6] != 0) b[medaly[i]+j][medalx[i]-j] = '2';
else pd[6] = 0;
if(medalx[i]-j>=1 && medaly[i]-j>=1 && b[medaly[i]-j][medalx[i]-j] != '0' && pd[7] != 0) b[medaly[i]-j][medalx[i]-j] = '2';
else pd[7] = 0;
if(medalx[i]+j<=m && medaly[i]-j>=1 && b[medaly[i]-j][medalx[i]+j] != '0' && pd[8] != 0) b[medaly[i]-j][medalx[i]+j] = '2';
else pd[8] = 0;
}
int head = 0,tail = 1,pdget = 0; //pdget用于判断是否到达过能看到奖杯的地方
bfs[1][0] = hx[i];bfs[1][1] = hy[i];
do {
head++;
for(int i = 1; i <= 4; i++) {
int x = bfs[head][0]+dir[i][0],y = bfs[head][0]+dir[i][1];
if(x >= 1 && x <= m && y >= 1 && y <= n && b[y][x] != '0' && b[y][x] != '3') {
tail++;bfs[tail][0] = x; bfs[tail][1] = y;bfs[tail][2] += 1;
if(b[y][x] == '2') { //到达能看到奖杯的地方
printf("%d\n", bfs[tail][2]);
head=tail; //找到最短路经,跳出while循环
pdget = 1;
break;
}
b[y][x] = '3';
}
}
}while(head<tail);
if(!pdget) printf("Poor Harry\n");
//重置b数组
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
//printf("%c ", b[i][j]);
if(b[i][j] == '2' || b[i][j] == '3') b[i][j] = '1';
}
//printf("\n");
}
}
return 0;
}