HDU 1242 Rescue

56 阅读 0 评论 37 点赞

我是靠谱客的博主老迟到星月，最近开发中收集的这篇文章主要介绍HDU 1242 Rescue，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

简单变形的广搜，而HDU 1026 Ignatius and the Princess I 是这道题的升级版，因为每个格子停留的时间可能不相同。

这里，天使的朋友可能有多个，所以我们从天使开始逆向去找他的朋友，最先找到他的朋友就是最短时间。

题目的变形在于多了守卫，每当一个守卫进入队列，第一次只扩展当前位置，仅仅是时间加1，第二次再向四个方向扩展。

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <queue>
 6 using namespace std;
 7
 8 struct Point
 9 {
10
int x, y;
11
int steps;
12 }start;
13
14 int row, col;
15 int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
16 int vis[205][205];
17 char map[205][205];
18
19 void BFS(void)
20 {
21
queue<Point> qu;
22
start.steps = 0;
23 
qu.push(start);
24
while(!qu.empty())
25 
{
26
Point fir = qu.front();
27
if(map[fir.x][fir.y] == 'r')
28 
{
29
printf("%dn", fir.steps);
30
return;
31 
}
32
if(map[fir.x][fir.y] == 'x')
33
{//第一次停留在原地
34 
Point next;
35
next.x = fir.x, next.y = fir.y, next.steps = fir.steps + 1;
36
map[fir.x][fir.y] = '.';//记得改变'x'，下一次变开始向四周扩展
37 
qu.push(next);
38 
qu.pop();
39
continue;
40 
}
41
for(int i = 0; i < 4; ++i)
42 
{
43
int xx = fir.x + dir[i][0];
44
int yy = fir.y + dir[i][1];
45
if(xx<0 || xx>=row || yy<0 || yy>=col || vis[xx][yy] || map[xx][yy]=='#')
46
continue;
47
else
48 
{
49 
Point next;
50
next.x = xx, next.y = yy, next.steps = fir.steps + 1;
51
vis[xx][yy] = 1;
52 
qu.push(next);
53 
}
54 
}
55 
qu.pop();
56 
}
57
printf("Poor ANGEL has to stay in the prison all his life.n");
58 }
59
60 int main(void)
61 {
62 
#ifdef LOCAL
63
freopen("1242in.txt", "r", stdin);
64
#endif
65
66
while(scanf("%d%d", &row, &col) == 2)
67 
{
68 
getchar();
69
for(int i = 0; i < row; ++i)
70 
{
71
for(int j = 0; j < col; ++j)
72 
{
73
scanf("%c", &map[i][j]);
74
if(map[i][j] == 'a')
75
start.x = i, start.y = j;
76 
}
77 
getchar();
78 
}
79
80
memset(vis, 0, sizeof(vis));
81
map[start.x][start.y] = '#';
82
vis[start.x][start.y] = 1;
83 
BFS();
84 
}
85
return 0;
86 }