ZOJ:1649 Rescue

77 阅读 0 评论 51 点赞

我是靠谱客的博主真实爆米花，这篇文章主要介绍ZOJ:1649 Rescue，现在分享给大家，希望可以做个参考。

发现自己对BFS理解还是很肤浅。

BFS可以来求最优解，尤其是像步数最少的这种。这个题虽然不是，但是可以特殊处理一下。

在BFS搜索过程中，到达（x，y）时如果所花费的时间比之前走到此处所花费时间要少，就把该点（x，y）放入队列。

注意一下，这个题不能一到达目的点就退出BFS，因为这是无法保证得到的结果是花费的最少时间，而第一次到达仅仅是步数最少。必须等到BFS过程结束即队列为空才可以得出结论。

另外，这个题没有把已访问点设置vis数组，也就是说访问过的位置还是尅月再次访问的，那么BFS会不会无限搜索下去呢？实际上是不会的，只有到达（x，y）所用时间更少才会重复入队，因为到达某点（x，y）花费的最少时间肯定是有下界的，所以不会无限搜索下去。

复制代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 100000000
using namespace std;
int m[5][2]= {{1,0},{0,1},{-1,0},{0,-1}};
struct Point
{
int x,y,cost;
Point():cost(INF) {}
Point(int a,int b,int c):x(a),y(b),cost(c) {}
};
int N,M;
bool Judge(int x,int y)
{
if(0<=x&&x<N&&0<=y&&y<M) return true;
return false;
}
int main()
{
while(scanf("%d%d",&N,&M)!=EOF)
{
char grid[205][205]= {0};
Point p[205][205];
int sx,sy,ex,ey;
for(int i=0; i<N; ++i)
{
scanf("%s",grid[i]);
for(int j=0; grid[i][j]; ++j)
if(grid[i][j]=='r')
{
sx=i;
sy=j;
}
else if(grid[i][j]=='a')
{
ex=i;
ey=j;
}
}
queue<Point> q;
q.push(Point(sx,sy,0));
while(!q.empty())
{
Point t=q.front();
q.pop();
int tx=t.x,ty=t.y;
for(int i=0; i<4; ++i)
{
int xx=tx+m[i][0],yy=ty+m[i][1];
if(Judge(xx,yy)&&grid[xx][yy]!='#')
{
int tmp;
if(grid[xx][yy]=='x') tmp=2;
else tmp=1;
if(p[xx][yy].cost>t.cost+tmp)
{
p[xx][yy].cost=t.cost+tmp;
p[xx][yy].x=xx;
p[xx][yy].y=yy;
q.push(p[xx][yy]);
}
}
}
}
if(p[ex][ey].cost==INF) puts("Poor ANGEL has to stay in the prison all his life.");
else printf("%dn",p[ex][ey].cost);
}
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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 100000000
using namespace std;
int m[5][2]= {{1,0},{0,1},{-1,0},{0,-1}};
struct Point
{
int x,y,cost;
Point():cost(INF) {}
Point(int a,int b,int c):x(a),y(b),cost(c) {}
};
int N,M;
bool Judge(int x,int y)
{
if(0<=x&&x<N&&0<=y&&y<M) return true;
return false;
}
int main()
{
while(scanf("%d%d",&N,&M)!=EOF)
{
char grid[205][205]= {0};
Point p[205][205];
int sx,sy,ex,ey;
for(int i=0; i<N; ++i)
{
scanf("%s",grid[i]);
for(int j=0; grid[i][j]; ++j)
if(grid[i][j]=='r')
{
sx=i;
sy=j;
}
else if(grid[i][j]=='a')
{
ex=i;
ey=j;
}
}
queue<Point> q;
q.push(Point(sx,sy,0));
while(!q.empty())
{
Point t=q.front();
q.pop();
int tx=t.x,ty=t.y;
for(int i=0; i<4; ++i)
{
int xx=tx+m[i][0],yy=ty+m[i][1];
if(Judge(xx,yy)&&grid[xx][yy]!='#')
{
int tmp;
if(grid[xx][yy]=='x') tmp=2;
else tmp=1;
if(p[xx][yy].cost>t.cost+tmp)
{
p[xx][yy].cost=t.cost+tmp;
p[xx][yy].x=xx;
p[xx][yy].y=yy;
q.push(p[xx][yy]);
}
}
}
}
if(p[ex][ey].cost==INF) puts("Poor ANGEL has to stay in the prison all his life.");
else printf("%dn",p[ex][ey].cost);
}
return 0;
}