1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 using namespace std; 5  6 const int MAX=205; 7 const int inf=1000000; 8 int tim[MAX][MAX]; 9 char maze[MAX][MAX];10 int n,m;11 int ai,aj;12 typedef struct c{13     int i,j,ti;14     bool operator <(const c &A)const {15         if(ti>A.ti) return true;16         return false;17     }18 }Node;19 Node tmp,pushed;20 priority_queue<Node>que;21 int dir[4][2]={0,1,0,-1,1,0,-1,0};22 23 bool ok(int i,int j){24     if(i>=0&&i<n&&j>=0&&j<m&&maze[i][j]!=‘#‘)25     return true;26     return false;27 }28 29 bool bfs(){30     int ti,tj;31     while(!que.empty()){32         tmp=que.top();33         que.pop();34         if(maze[tmp.i][tmp.j]==‘r‘){35             printf("%d\n",tmp.ti);36             return true;37         }38         for(int i=0;i<4;i++){39             ti=tmp.i+dir[i][0];40             tj=tmp.j+dir[i][1];41             if(ok(ti,tj)){42                 if(maze[ti][tj]==‘.‘||maze[ti][tj]==‘r‘){43                     if(tmp.ti+1<tim[ti][tj]){44                         tim[ti][tj]=tmp.ti+1;45                         pushed.i=ti; pushed.j=tj; pushed.ti=tmp.ti+1;46                         que.push(pushed);47                     }48                 }49                 else if(maze[ti][tj]==‘x‘){50                     if(tmp.ti+2<tim[ti][tj]){51                         tim[ti][tj]=tmp.ti+2;52                         pushed.i=ti; pushed.j=tj; pushed.ti=tmp.ti+2;53                         que.push(pushed);54                     }55                 }56             }57         }58     }59     return false;60 }61 62 int main(){63     while(scanf("%d%d",&n,&m)!=EOF){64         for(int i=0;i<n;i++){65             scanf("%s",maze[i]);66             for(int j=0;j<m;j++){67                 if(maze[i][j]==‘a‘){68                     ai=i; aj=j;69                 }70                 tim[i][j]=inf;71             }72         }73         tim[ai][aj]=0;74         tmp.i=ai; tmp.j=aj; tmp.ti=0;75         que.push(tmp);76         if(!bfs()){77             printf("Poor ANGEL has to stay in the prison all his life.\n");78         }79         while(!que.empty())80         que.pop();81     }82     return 0;83 }