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

#include<stdio.h>
int inf=9999999;
char map[220][220];
int dis[220][220];
int n,m;
int mn,mm;
int en,em;
void bfs(int tn,int tm) {
	if(tm+1<m&&((map[tn][tm+1]=='.'&&dis[tn][tm+1]>=dis[tn][tm]+1)||(map[tn][tm+1]=='x'&&dis[tn][tm+1]>=dis[tn][tm]+2))) {
		dis[tn][tm+1]=dis[tn][tm]+1;
		if(map[tn][tm+1]=='x')
			dis[tn][tm+1]++;
		bfs(tn,tm+1);
	}
	if(tm-1>=0&&((map[tn][tm-1]=='.'&&dis[tn][tm-1]>=dis[tn][tm]+1)||(map[tn][tm-1]=='x'&&dis[tn][tm-1]>=dis[tn][tm]+2))) {
		dis[tn][tm-1]=dis[tn][tm]+1;
		if(map[tn][tm-1]=='x')
			dis[tn][tm-1]++;
		bfs(tn,tm-1);
	}
	if(tn-1>=0&&((map[tn-1][tm]=='.'&&dis[tn-1][tm]>=dis[tn][tm]+1)||(map[tn-1][tm]=='x'&&dis[tn-1][tm]>=dis[tn][tm]+2))) {
		dis[tn-1][tm]=dis[tn][tm]+1;
		if(map[tn-1][tm]=='x')
			dis[tn-1][tm]++;
		bfs(tn-1,tm);
	}
	if(tn+1<n&&((map[tn+1][tm]=='.'&&dis[tn+1][tm]>=dis[tn][tm]+1)||(map[tn+1][tm]=='x'&&dis[tn+1][tm]>=dis[tn][tm]+2))) {
		dis[tn+1][tm]=dis[tn][tm]+1;
		if(map[tn+1][tm]=='x')
			dis[tn+1][tm]++;
		bfs(tn+1,tm);
	}
}
int main() {
	while(scanf("%d %d",&n,&m)!=EOF) {
		getchar();
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				dis[i][j]=inf;
				scanf("%c",&map[i][j]);
				if(map[i][j]=='r') {
					mn=i;
					mm=j;
					dis[i][j]=0;
				} else if(map[i][j]=='a') {
					en=i;
					em=j;
					map[i][j]='.';
				}
			}
			getchar();
		}
		bfs(mn,mm);
		if(dis[en][em]==inf)
			printf("Poor ANGEL has to stay in the prison all his life.\n");
		else
			printf("%d\n",dis[en][em]);
	}
	return 0;
}