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

题目链接：

题目大意：

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

思路：

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

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<queue>
 7 #include<stack>
 8 #include<map>
 9 #include<set>
10 #include<sstream>
11 #include<functional>
12 using namespace std;
13 typedef long long ll;
14 const int maxn = 2e2 + 10;
15 const int INF = 1e9 + 7;
16 int T, n, m, cases;
17 int dir[][2] = {1,0,0,1,-1,0,0,-1};
18 struct node
19 {
20     int x, y, time;
21     bool operator <(const node& a)const
22     {
23         return time > a.time;
24     }
25     node(){}
26     node(int x, int y, int time):x(x), y(y), time(time){}
27 };
28 char Map[maxn][maxn];
29 bool vis[maxn][maxn];
30 bool judge(int x, int y)
31 {
32     return (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && Map[x][y] != '#');
33 }
34 void bfs(int x, int y)
35 {
36     memset(vis, 0, sizeof(vis));
37     priority_queue<node>q;
38     q.push(node(x, y, 0));
39     vis[x][y] = 1;
40     while(!q.empty())
41     {
42         node now = q.top();
43         q.pop();
44         if(Map[now.x][now.y] == 'r')
45         {
46             cout<<now.time<<endl;
47             return;
48         }
49         for(int i = 0; i < 4; i++)
50         {
51             node next = now;
52             next.x += dir[i][0];
53             next.y += dir[i][1];
54             if(judge(next.x, next.y))
55             {
56                 vis[next.x][next.y] = 1;
57                 next.time++;
58                 if(Map[next.x][next.y] == 'x')next.time++;
59                 q.push(next);
60             }
61         }
62     }
63     printf("Poor ANGEL has to stay in the prison all his life.
");
64     return;
65 }
66 int main()
67 {
68     while(cin >> n >> m)
69     {
70         int sx, sy;
71         for(int i = 0; i < n; i++)
72         {
73             cin >> Map[i];
74             for(int j = 0; j < m; j++)if(Map[i][j] == 'a')sx = i, sy = j;
75         }
76         bfs(sx, sy);
77     }
78     return 0;
79 }