P2199 最后的迷宫

题目描述

哈利的视力非常好，他能从迷宫的一端沿直线看到迷宫的另一端（但他只能看八个方向——东北，东，东南，南，西南……），而且跑得非常快，跑一步（向上、下、左、右移动一格）只需要1s。但迷宫是不透光的，而且，要烧掉迷宫的墙也不容易，所以哈利决定绕到一个能够看到奖杯的地方。现在，哈利希望你能帮他确定最短需要多长时间才能拿到奖杯。

输入格式

第一行为2个数N，M表示迷宫的规模（N为高，M为宽）

接下来是N*M的迷宫，O表示空地，X表示墙。

最后是多对数据，分别是奖杯坐标及哈利的坐标（显然不可能在墙上），每对占一行，0为结束标志。

输出格式

根据每对数据，计算哈利拿到奖杯的最短时间，每对一行。如果魔法部有意难为选手，用墙将奖杯包围了起来，输出”Poor Harry”。

输入输出样例

输入 #1

1
2
3
4
5
6
7
3 4
OXXO
XXOO
XOOO
3 2 2 4
3 3 1 1
0 0 0 0

输出 #1

1
2
1
Poor Harry

hint

对于30%的数据,有N*M<=100

对于60%的数据,有N*M<=1600

对于100%的数据,有N*m<=16384

二维数组总大小 <= 16384 , 所以用一维数组表示二维数组。

剩下就是跑 bfs ,每次先初始化出可以看到终点的所有点并标记，然后搜索的时候判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
const int MAX=16384+10;
int n,m,fx,fy,ex,ey;
char a[MAX];
int vis[MAX];
int aw[4][2]={-1,0,0,1,1,0,0,-1};
int aw2[8][2]={-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};
struct node{
	int x,y,c;
	node(int _x,int _y,int _c){
		x=_x;y=_y;c=_c;
	}
};
inline bool judge(int x,int y){
	if(x<1||x>n||y<1||y>m) return false;
	return true;
}
inline void isok(int d){
	int x,y;
	fi(i,0,8){
		x=ex,y=ey;
		while(judge(x,y) && a[(x-1)*m+y-1]!='X'){
			vis[(x-1)*m+y-1] = d;
			x += aw2[i][0];
			y += aw2[i][1];
		}
	}
}
int  bfs(int d){
	queue<node>q;
	q.push(node(fx,fy,0));
	vis[(fx-1)*m+fy-1]=d;
	isok(d+1);
	if(vis[(fx-1)*m+fy-1] == d+1) return 0;
	while(!q.empty()){
		node t = q.front();
		q.pop();
		fi(i,0,4){
			int tx = t.x + aw[i][0],ty = t.y + aw[i][1];
			if(judge(tx,ty) && vis[(tx-1)*m+ty-1]!=d && a[(tx-1)*m+ty-1]!='X'){
				if(vis[(tx-1)*m+ty-1] == d+1) return t.c + 1;
				else {
					vis[(tx-1)*m+ty-1]= d ;
					q.push(node(tx,ty,t.c + 1));
				}
			}
		}
	}
	return -1;
}
int main(){
	freopen("in","r",stdin);
	mem(vis,0);
	sf(n);sf(m);
	fi(i,0,n) {
		scanf("%s",a+(i*m)); 
	}
	int cnt=1;
	while(~sf(ex)&&ex){
		sf(ey);sf(fx);sf(fy);
		int ans = bfs(cnt);
		cnt +=2;
		if(ans == -1) pfc("Poor Harry\n");
		else pfn(ans);
	}
	return 0;
}