ZOJ 1649

这题要用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;
}