这题要用BFS去做，要注意的是’x‘，这里可以有优先队列去做，会很简单；

另一个要注意的是，a只有一个，r可能有很多个，所以可以用a去找最接近的r；

 

 

 

#include <iostream>

#include <queue>

#include "string.h"

using namespace std;

struct step{

    int x,y,t;

    void init(int xx,int yy,int tt){

        x=xx;

        y=yy;

        t=tt;

    }

};

int n,m,sx,sy;

bool visited[200][200];

int dir[4][2]={

{1,0},{-1,0},{0,-1},{0,1}};

char road[200][200];

bool operator<(step a, step b)

{

    return a.t > b.t;

}

int bfs(){

    memset(visited, 0 , sizeof(visited));

    priority_queue<step> q;

    step start;

    start.init(sx,sy,0);

    q.push(start);

    visited[sy][sx]=1;

    while(!q.empty()){

        step k=q.top();

        q.pop();

        int x=k.x,y=k.y,t=k.t;

        for(int i=0;i<4;i++){

            int nx=x+dir[i][0];

            int ny=y+dir[i][1];

            if(nx<0||nx>m||ny<0||ny>n||visited[ny][nx])continue;

            if(road[ny][nx]!='r'&&road[ny][nx]!='x'&&road[ny][nx]!='.'){continue;}

            if(road[ny][nx]=='r'){return t+1;}

            if(road[ny][nx]=='x'){

                step s;

                s.init(nx,ny,t+2);

                q.push(s);

                visited[ny][nx]=true;

                continue;

            }

            step s;

            s.init(nx,ny,t+1);

            q.push(s);

            visited[ny][nx]=true;

        }

    }

    return -1;

}

int main(){

    while(cin>>n>>m){

        for(int i=0;i<n;i++){

            for(int j=0;j<m;j++){

                cin>>road[i][j];

                if(road[i][j]=='a'){

                    sx=j;

                    sy=i;

                }

            }

        }

        int time=bfs();

        if(time==-1)cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;

        else cout<<time<<endl;

    }

    return 0;

}