HDU 1242 Rescue

80 阅读 0 评论 53 点赞

我是靠谱客的博主老迟到星月，这篇文章主要介绍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 }

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
 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 }