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

89 阅读 0 评论 59 点赞

我是靠谱客的博主从容唇彩，这篇文章主要介绍ZOJ Problem Set - 1649 Rescue BFS+优先队列ZOJ Problem Set - 1649 Rescue，现在分享给大家，希望可以做个参考。

ZOJ Problem Set - 1649 Rescue

题目描述：

　　题目链接：ZOJ Problem Set - 1649 Rescue

题目大意：

　　 Angel 被关在牢房里，你要从给定的地方出发在最短时间内找到天使。单位时间内能向上下左右移动一个。并且牢房里理由狱警，遇到狱警所消耗时间 +1 。如果，没有办法找到 Angel ，那么输出： Poor ANGEL has to stay in the prison all his life.

解题思路：

　　因为题目要求最少操作数，即求从初始地点到目标地点的最短路，即使用 BFS 。又因为， . 和x对应的权值不一样，所以用优先队列，使操作数少的状态优先出队。

复杂度分析:

时间复杂度： O(n∗m)
空间复杂度： O(n∗m)

AC代码：

复制代码

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
struct node{
int step;
int x,y;
bool operator < (const node &a)const{
return step > a.step;
}
};
const int maxn = 210;
int pri[maxn][maxn];
int n,m;
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int bfs(int x0,int y0){
priority_queue<node>Q;
node tmp;
tmp.x = x0;
tmp.y = y0;
tmp.step = 0;
Q.push(tmp);
while(!Q.empty()){
tmp = Q.top();
Q.pop();
for(int i = 0; i < 4; i++){
int xt = tmp.x + dir[i][0];
int yt = tmp.y + dir[i][1];
if(xt < m && xt >= 0 && yt < n && yt >= 0){
if(pri[xt][yt] == 3)return tmp.step + 1;
if(pri[xt][yt]){
node tmp2;
tmp2.x = xt;
tmp2.y = yt;
tmp2.step = tmp.step + pri[xt][yt];
Q.push(tmp2);
pri[xt][yt] = 0;
}
}
}
}
return -1;
}
int main(){
int x0,y0;
while(scanf("%d %d",&n ,&m) != EOF){
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++){
char t = getchar();
while(t == 'n') t = getchar();
switch(t){
case '#':pri[i][j] = 0;break;
case 'a':pri[i][j] = 3;break;
case 'x':pri[i][j] = 2;break;
case '.':pri[i][j] = 1;break;
case 'r':x0 = i; y0 = j;
}
}
int ans = bfs(x0,y0);
if(ans != -1)printf("%dn",ans);
else printf("Poor ANGEL has to stay in the prison all his life.n");
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
struct node{
int step;
int x,y;
bool operator < (const node &a)const{
return step > a.step;
}
};
const int maxn = 210;
int pri[maxn][maxn];
int n,m;
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int bfs(int x0,int y0){
priority_queue<node>Q;
node tmp;
tmp.x = x0;
tmp.y = y0;
tmp.step = 0;
Q.push(tmp);
while(!Q.empty()){
tmp = Q.top();
Q.pop();
for(int i = 0; i < 4; i++){
int xt = tmp.x + dir[i][0];
int yt = tmp.y + dir[i][1];
if(xt < m && xt >= 0 && yt < n && yt >= 0){
if(pri[xt][yt] == 3)return tmp.step + 1;
if(pri[xt][yt]){
node tmp2;
tmp2.x = xt;
tmp2.y = yt;
tmp2.step = tmp.step + pri[xt][yt];
Q.push(tmp2);
pri[xt][yt] = 0;
}
}
}
}
return -1;
}
int main(){
int x0,y0;
while(scanf("%d %d",&n ,&m) != EOF){
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++){
char t = getchar();
while(t == 'n') t = getchar();
switch(t){
case '#':pri[i][j] = 0;break;
case 'a':pri[i][j] = 3;break;
case 'x':pri[i][j] = 2;break;
case '.':pri[i][j] = 1;break;
case 'r':x0 = i; y0 = j;
}
}
int ans = bfs(x0,y0);
if(ans != -1)printf("%dn",ans);
else printf("Poor ANGEL has to stay in the prison all his life.n");
}
}