1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5  6 int n , m; 7 const int size = 210; 8 int dir[4][2]={1,0,-1,0,0,1,0,-1};  9 char maze[size][size];10 bool vis[size][size];11 struct data12 {13     int x;14     int y;15     int step;16     bool operator < (const data& p )const17     {18         return p.step<step;19     }20 }st , end;21 22 int bfs( )23 {24     priority_queue<data> q;25     data now , next;26     int xx , yy;27     memset( vis , false , sizeof(vis) );28     while( !q.empty() )29         q.pop();30     q.push( st );31     vis[ st.x ][ st.y ] = true;32     while( !q.empty() )33     {34         now = q.top();35         q.pop();36         if( now.x == end.x && now.y == end.y )37             return now.step;38         for( int i = 0 ; i<4 ; i++ )39         {40             xx = now.x + dir[i][0];41             yy = now.y + dir[i][1];42             if( xx>=0 && xx<n && yy>=0 && yy<m && maze[xx][yy]!=‘#‘ && !vis[xx][yy] )43             {44                 if( maze[xx][yy] == ‘x‘ )45                     next.step = now.step + 2;46                 else47                     next.step = now.step + 1;48                 next.x = xx;49                 next.y = yy;50                 vis[xx][yy] = true;51                 q.push( next );52             }53         }54     }55     return -1;56 }57 58 int main()59 {60     int ans;61     while( cin >> n >> m )62     {63         for( int i = 0 ; i<n ; i++ )64         {65             for( int j = 0 ; j<m ; j++ )66             {67                 cin >> maze[i][j];68                 if( maze[i][j] == ‘a‘ )69                 {70                     st.x = i;71                     st.y = j;72                     st.step = 0;    73                 }74                 else if( maze[i][j] == ‘r‘ )75                 {76                     end.x = i;77                     end.y = j;78                 }79             }80         }81         ans = bfs();82         if( -1 == ans )83             cout << "Poor ANGEL has to stay in the prison all his life." << endl;            84         else85             cout << ans << endl;86     }87     return 0;88 }