HDU 1242 Rescue-蒲公英云

HDU 1242 Rescue

怼烎@ 2022-04-16 04:59 262阅读 0赞

原题目链接HDU1242

分类

HDU 搜索 BFS 优先队列

题意

X代表卫兵，a代表终点，r代表起始点，.代表路，#代表墙

路花费一秒，x花费两秒

问到达终点的最少时间

样例输入输出

Sample Input

7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........

Sample Output

想法

BFS+优先队列的裸题(第一次不看题解写出来的优先队列题，虽然是最基础的题目，赞)

代码

93ms

#include<bits/stdc++.h>
#define maxn 1111
using namespace std;
int n,m;
int sx,sy;
char Map[maxn][maxn];
int vis[maxn][maxn];
int dis[4][2] = { { -1,0},{ 0,-1},{ 0,1},{ 1,0}};
struct node{ 
    int x,y,step;
    friend bool operator < (node a,node b){ 
        return b.step<a.step;
    }
};
bool check(int x,int y){ 
    if(x>=0&&x<n&&y>=0&&y<m&&!vis[x][y]&&Map[x][y]!='#') return true;
    return false;
}
int bfs(int x,int y){ 
    priority_queue <node> q;
    node s;
    s.x = x;
    s.y = y;
    s.step = 0;
    vis[x][y] =1;
    q.push(s);
    while(!q.empty()){ 
        node temp1 = q.top();
        q.pop();
        for(int i=0;i<4;i++){ 
            node temp2 = temp1;
            temp2.x+=dis[i][0];
            temp2.y+=dis[i][1];
            temp2.step+=1;
            if(check(temp2.x,temp2.y)){ 
                if(Map[temp2.x][temp2.y]=='a')
                    return temp2.step;
                if(Map[temp2.x][temp2.y]=='x')
                    temp2.step++;
                vis[temp2.x][temp2.y] = 1;
                q.push(temp2);
            }
        }
    }
    return 0;
}
int main()
{ 
    while(scanf("%d%d",&n,&m)!=EOF){ 
        for(int i=0;i<n;i++){ 
            scanf("%s",Map[i]);
            for(int j =0;j<m;j++){ 
                if(Map[i][j]=='r'){ 
                    sx = i;
                    sy = j;
                }
            }
        }
        memset(vis,0,sizeof(vis));
        int ans = bfs(sx,sy);
        if(ans){ 
            printf("%d\n",ans);
        }else{ 
            printf("Poor ANGEL has to stay in the prison all his life.\n");
        }
    }
    return 0;
}