Rescue BFS+优先队列杭电1242

71 阅读 0 评论 47 点赞

我是靠谱客的博主虚心航空，这篇文章主要介绍Rescue BFS+优先队列杭电1242，现在分享给大家，希望可以做个参考。

复制代码

思路 ： 优先队列
每次都取最小的时间，遇到了终点直接就输出#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=200;
int n,m,sa,ea,sr,er;
char arr[N][N];
int bb[N][N]={0};
struct stu{
int a,b;
int time;
bool friend operator <(const stu &a,const stu &b){
return a.time>b.time;
}
};
int a[4]={0,1,0,-1};
int br[4]={1,0,-1,0};
void bfs(){
priority_queue<stu>que;
stu s;
s.a=sa;
s.b=ea;
s.time=0;
que.push(s);
bb[sa][ea]=1;
int flag=0;
while(que.size()){
stu p;
p=que.top();
que.pop();
stu st;
for(int i=0;i<4;i++){
st.a=p.a+a[i];
st.b=p.b+br[i];
if(st.a>=0&&st.b>=0&&st.a<n&&st.b<m&&bb[st.a][st.b]!=1&&arr[st.a][st.b]!='#'){
bb[st.a][st.b]=1;
if(arr[st.a][st.b]=='x')
st.time=p.time+2;
else {
st.time=p.time+1;
}
que.push(st);
if(st.a==sr&&st.b==er)
{
cout<<st.time<<endl;
return ;
}
}
}
}
cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
return ;
}
int main()
{
while(cin>>n>>m){
memset(bb,0,sizeof(bb));
for(int i=0;i<n;i++)
scanf("%s",&arr[i]);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
{
if(arr[i][j]=='a'){
sa=i;
ea=j;
}
else if(arr[i][j]=='r'){
sr=i;
er=j;
}
}
}
bfs();
}
return 0;
}

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
66
67
68
69
70
71
72
73
74
75
76
77
思路 ： 优先队列
每次都取最小的时间，遇到了终点直接就输出

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=200;
int n,m,sa,ea,sr,er;
char arr[N][N];
int bb[N][N]={0};
struct stu{
int a,b;
int time;
bool friend operator <(const stu &a,const stu &b){
return a.time>b.time;
}
};
int a[4]={0,1,0,-1};
int br[4]={1,0,-1,0};
void bfs(){
priority_queue<stu>que;
stu s;
s.a=sa;
s.b=ea;
s.time=0;
que.push(s);
bb[sa][ea]=1;
int flag=0;
while(que.size()){
stu p;
p=que.top();
que.pop();
stu st;
for(int i=0;i<4;i++){
st.a=p.a+a[i];
st.b=p.b+br[i];
if(st.a>=0&&st.b>=0&&st.a<n&&st.b<m&&bb[st.a][st.b]!=1&&arr[st.a][st.b]!='#'){
bb[st.a][st.b]=1;
if(arr[st.a][st.b]=='x')
st.time=p.time+2;
else {
st.time=p.time+1;
}
que.push(st);
if(st.a==sr&&st.b==er)
{
cout<<st.time<<endl;
return ;
}
}
}
}
cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
return ;
}
int main()
{
while(cin>>n>>m){
memset(bb,0,sizeof(bb));
for(int i=0;i<n;i++)
scanf("%s",&arr[i]);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
{
if(arr[i][j]=='a'){
sa=i;
ea=j;
}
else if(arr[i][j]=='r'){
sr=i;
er=j;
}
}
}
bfs();
}
return 0;
}