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

57 阅读 0 评论 38 点赞

我是靠谱客的博主糊涂帽子，最近开发中收集的这篇文章主要介绍ZOJ-1649 Rescue---BFS+优先队列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：

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

题目大意：

天使的朋友要去救天使，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.n");
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 }