1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define inf 99999
 5 using namespace std;
 6 
 7 char graph[205][205];
 8 bool visit[205][205];
 9 int dp[205][205];
10 int m,n,cnt;
11 int ex,ey,sx,sy;
12 int d[4][2]={1,0,0,1,0,-1,-1,0};
13 
14 void dfs(int x,int y)
15 {
16     if(dp[x][y]>=dp[ex][ey])return;
17     for(int i=0;i<4;i++)
18     {
19         int xx=x+d[i][0];
20         int yy=y+d[i][1];
21         if(xx<0||xx>=m||yy<0||yy>=n||graph[xx][yy]==‘#‘||visit[xx][yy]==false)continue;
22         if(graph[xx][yy]==‘x‘)
23         {
24             if(dp[xx][yy]==-1||dp[xx][yy]>dp[x][y]+2)
25             dp[xx][yy]=dp[x][y]+2;
26             else continue;
27         }
28         else if(graph[xx][yy]==‘a‘)
29         {
30             if(dp[xx][yy]==-1||dp[xx][yy]>dp[x][y]+1)
31             dp[xx][yy]=dp[x][y]+1;
32             return;
33         }
34         else if(graph[xx][yy]==‘.‘)
35         {
36             if(dp[xx][yy]==-1||dp[xx][yy]>dp[x][y]+1)
37             dp[xx][yy]=dp[x][y]+1;
38             else continue;
39         }
40         visit[xx][yy]=false;
41         dfs(xx,yy);
42         visit[xx][yy]=true;
43     }
44 }
45 
46 int main()
47 {
48 //    freopen("in.txt","r",stdin);
49     int i,j;
50     while(scanf("%d%d",&m,&n)!=EOF)
51     {
52         ex=ey=-1;
53         memset(visit,1,sizeof(visit));
54         for(i=0;i<m;i++)
55         scanf("%s",graph[i]);
56         for(i=0;i<m;i++)
57         for(j=0;j<n;j++)
58         {
59             dp[i][j]=-1;
60             if(graph[i][j]==‘r‘)
61             sx=i,sy=j;
62             else if(graph[i][j]==‘a‘)
63             dp[i][j]=inf,ex=i,ey=j;
64             else continue;
65         }
66         if(ex==-1&&ey==-1)
67         {
68             printf("Poor ANGEL has to stay in the prison all his life.\n");
69             continue;
70         }
71         dp[sx][sy]=0;
72         dfs(sx,sy);
73         if(dp[ex][ey]!=inf)
74         printf("%d\n",dp[ex][ey]);
75         else
76         printf("Poor ANGEL has to stay in the prison all his life.\n");
77     }
78     return 0;
79 }