HDU 1242 Rescue (BFS + 优先队列)-蒲公英云

HDU 1242 Rescue (BFS + 优先队列)

青旅半醒 2024-02-17 18:56 153阅读 0赞

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=200+10;
char p[maxn][maxn];        //保存字符
int d[maxn][maxn];          //从开始位置到当前位置花的时间长度
struct node{
    int x,y;
    node(int x1=0,int y1=0):x(x1),y(y1){}
    bool operator<(const node & n)const{
    return d[x][y]>d[n.x][n.y];
    }
};
node a;
node r;
int N,M;
const int dir[][2]={
    {-1,0},{1,0},{0,-1},{0,1}};
bool isValid(const node &v){                  
    return v.x>=0 && v.x<N && v.y>=0 && v.y<M;
}
void bfs(){
    priority_queue<node>q;          //优先队列，整数值越小越先出队列
    q.push(r);
    memset(d,0,sizeof(d));
    while(!q.empty()){
        node u=q.top();q.pop();
        if(u.x== a.x && u.y== a.y){           //如果找到 Angel 就 输出所花时间 并退出 BFS
         printf("%d\n",d[u.x][u.y]);    
         return ;        
        }
        for(int i=0;i<4;i++){
            node v=node(u.x+dir[i][0],u.y+dir[i][1]);
            if(isValid(v)&& !d[v.x][v.y] && p[v.x][v.y]!='#'){
                if(p[v.x][v.y]=='x')d[v.x][v.y]=d[u.x][u.y]+2;
                else d[v.x][v.y]=d[u.x][u.y]+1;
                 q.push(v);
            }
        }
    }
printf ("Poor ANGEL has to stay in the prison all his life.\n");
}
int main(){
    while(scanf("%d%d",&N,&M)==2){
        memset(p,0,sizeof(p));
        for(int i=0;i<N;i++)scanf("%s",p[i]);
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(p[i][j]=='a'){
                    a.x=i;a.y=j;
                }
                else if(p[i][j]=='r'){
                    r.x=i;r.y=j;
                }
            }
        }
        bfs();
    }
    return 0;
}