杭电1242Rescue题(bfs+优先队列)杭电1242Rescue题(bfs+优先队列)

84 阅读 0 评论 56 点赞

我是靠谱客的博主悦耳黄豆，这篇文章主要介绍杭电1242Rescue题(bfs+优先队列)杭电1242Rescue题(bfs+优先队列)，现在分享给大家，希望可以做个参考。

杭电1242Rescue题(bfs+优先队列)

题目链接~~>

这题是学习优先队列的第一题搞了好久才AC：

先介绍一下优先队列：

头文件：

复制代码

1
2
 #include<queue>
using namespace std;

由大到小出队：

复制代码

1
2
3
4
5
6
7
8
9
10
11

struct zhang
{
int x,y;
friend bool operator<(const zhang &a,const zhang &b)
{
return a.x < b.x ;
}
};
priority_queue<zhang>q;
zhang current;

由小到大出队：
将上面的 return a .x < b.x ;中的 "<" 改为 “>” ；但传说中这种方法G++编译器编译不过；

（非本人）代码：

复制代码

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#define N 201
using namespace std;
//优先队列解决,广度优先
struct Persion
{
int x,y;
int time;
friend bool operator < (const Persion &a,const Persion &b)
{
return a.time>b.time; //">" 返回队列中较小的元素；"< " 则返回队列中较大的元素
}
};
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
char map[N][N];
int visited[N][N];
int m,n;
int BFS(int x,int y)
{
priority_queue <Persion>q;
Persion current,next;
memset(visited,0,sizeof(visited));
current.x=x;
current.y=y;
current.time=0;
visited[current.x][current.y]=1;
q.push(current);
while(!q.empty())
{
current=q.top();
q.pop();
for(int i=0;i<4;i++)
{
next.x=current.x+dir[i][0];
next.y=current.y+dir[i][1];
if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&map[next.x][next.y]!='#'&&!visited[next.x][next.y])
{
if(map[next.x][next.y]=='r')
return current.time+1;
if(map[next.x][next.y]=='x')
next.time=current.time+2;
else
next.time=current.time+1;
visited[next.x][next.y]=1;
q.push(next);
}
}
}
return -1;
}
int main()
{
int i,j;
Persion angle;
while(cin>>n>>m&&(m||n))
{
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
cin>>map[i][j];
if(map[i][j]=='a')
{
angle.x=i;
angle.y=j;
}
}
int time=BFS(angle.x,angle.y);
if(time==-1)
cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
else
cout<<time<<endl;
}
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
 复制代码#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#define N 201
using namespace std;
//优先队列解决,广度优先
struct Persion
{
int x,y;
int time;
friend bool operator < (const Persion &a,const Persion &b)
{
return a.time>b.time; //">" 返回队列中较小的元素；"< " 则返回队列中较大的元素
}
};
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
char map[N][N];
int visited[N][N];
int m,n;
int BFS(int x,int y)
{
priority_queue <Persion>q;
Persion current,next;
memset(visited,0,sizeof(visited));
current.x=x;
current.y=y;
current.time=0;
visited[current.x][current.y]=1;
q.push(current);
while(!q.empty())
{
current=q.top();
q.pop();
for(int i=0;i<4;i++)
{
next.x=current.x+dir[i][0];
next.y=current.y+dir[i][1];
if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&map[next.x][next.y]!='#'&&!visited[next.x][next.y])
{
if(map[next.x][next.y]=='r')
return current.time+1;
if(map[next.x][next.y]=='x')
next.time=current.time+2;
else
next.time=current.time+1;
visited[next.x][next.y]=1;
q.push(next);
}
}
}
return -1;
}
int main()
{
int i,j;
Persion angle;
while(cin>>n>>m&&(m||n))
{
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
cin>>map[i][j];
if(map[i][j]=='a')
{
angle.x=i;
angle.y=j;
}
}
int time=BFS(angle.x,angle.y);
if(time==-1)
cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
else
cout<<time<<endl;
}
return 0;
}
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#define N 201
using namespace std;
//优先队列解决,广度优先
struct Persion
{
int x,y;
int time;
friend bool operator < (const Persion &a,const Persion &b)
{
return a.time>b.time; //">" 返回队列中较小的元素；"< " 则返回队列中较大的元素
}
};
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
char map[N][N];
int visited[N][N];
int m,n;
int BFS(int x,int y)
{
priority_queue <Persion>q;
Persion current,next;
memset(visited,0,sizeof(visited));
current.x=x;
current.y=y;
current.time=0;
visited[current.x][current.y]=1;
q.push(current);
while(!q.empty())
{
current=q.top();
q.pop();
for(int i=0;i<4;i++)
{
next.x=current.x+dir[i][0];
next.y=current.y+dir[i][1];
if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&map[next.x][next.y]!='#'&&!visited[next.x][next.y])
{
if(map[next.x][next.y]=='r')
return current.time+1;
if(map[next.x][next.y]=='x')
next.time=current.time+2;
else
next.time=current.time+1;
visited[next.x][next.y]=1;
q.push(next);
}
}
}
return -1;
}
int main()
{
int i,j;
Persion angle;
while(cin>>n>>m&&(m||n))
{
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
cin>>map[i][j];
if(map[i][j]=='a')
{
angle.x=i;
angle.y=j;
}
}
int time=BFS(angle.x,angle.y);
if(time==-1)
cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
else
cout<<time<<endl;
}
return 0;
}



 
复制代码
复制代码
复制代码