ZOJ-1649 Rescue---BFS+优先队列

题目链接：

https://vjudge.net/problem/ZOJ-1649

题目大意：

天使的朋友要去救天使，a是天使，r 是朋友，x是卫兵。每走一步需要时间1，打倒卫兵需要另外的时间1，问救到天使所用的最少时间。注意存在救不到的情况。

思路：

BFS搜索，由于打倒卫兵时间为2，所以用BFS+优先队列做，每次出队时间最少的拓展，每个格子只走一次才是最优解

 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 #include<cmath>
 #include<queue>
 #include<stack>
 #include<map>
 #include<set>
 #include<sstream>
 #include<functional>
 using namespace std;
 typedef long long ll;
 const int maxn = 2e2 + ;
 const int INF = 1e9 + ;
 int T, n, m, cases;
 int dir[][] = {,,,,-,,,-};
 struct node
 {
     int x, y, time;
     bool operator <(const node& a)const
     {
         return time > a.time;
     }
     node(){}
     node(int x, int y, int time):x(x), y(y), time(time){}
 };
 char Map[maxn][maxn];
 bool vis[maxn][maxn];
 bool judge(int x, int y)
 {
     return (x >=  && x < n && y >=  && y < m && !vis[x][y] && Map[x][y] != '#');
 }
 void bfs(int x, int y)
 {
     memset(vis, , sizeof(vis));
     priority_queue<node>q;
     q.push(node(x, y, ));
     vis[x][y] = ;
     while(!q.empty())
     {
         node now = q.top();
         q.pop();
         if(Map[now.x][now.y] == 'r')
         {
             cout<<now.time<<endl;
             return;
         }
         for(int i = ; i < ; i++)
         {
             node next = now;
             next.x += dir[i][];
             next.y += dir[i][];
             if(judge(next.x, next.y))
             {
                 vis[next.x][next.y] = ;
                 next.time++;
                 if(Map[next.x][next.y] == 'x')next.time++;
                 q.push(next);
             }
         }
     }
     printf("Poor ANGEL has to stay in the * all his life.\n");
     return;
 }
 int main()
 {
     while(cin >> n >> m)
     {
         int sx, sy;
         for(int i = ; i < n; i++)
         {
             cin >> Map[i];
             for(int j = ; j < m; j++)if(Map[i][j] == 'a')sx = i, sy = j;
         }
         bfs(sx, sy);
     }
     return ;
 }