UVa 11931 - Maze Escape

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

類似倉庫番遊戲,必須將箱子推到指定的按鈕位置,才會開啟逃離門,每一次可以走一步,如果箱子在旁邊,則人與箱子會同時往同一個方向移動。求逃離最少步數。

在還沒有打開門之前,門就相當於障礙物存在,不能經過。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
3 3
d.b
.@.
x.#
3 5
...d.
.#x#.
...@b
0 0

Sample Output

1
2
No Way!
20

Solution

反例輸出有誤,把 No Way! 拆成兩行送出結果拿到 WA。

把人的位置和箱子位置記錄成一個狀態,得到 dist[sx][sy][bx][by] 進行 bfs 搜索即可。特別小心不可經過尚未開啟的門問題。

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
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int sx, sy, ex, ey, bx, by, cx, cy;
int n, m;
char g[32][32];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int dist[25][25][25][25];
int bfs() {
memset(dist, 0, sizeof(dist));
dist[sx][sy][bx][by] = 1;
queue<int> X, Y, BX, BY;
int x, y, tx, ty, ttx, tty;
X.push(sx), Y.push(sy), BX.push(bx), BY.push(by);
while (!X.empty()) {
x = X.front(), X.pop();
y = Y.front(), Y.pop();
bx = BX.front(), BX.pop();
by = BY.front(), BY.pop();
int step = dist[x][y][bx][by];
for (int i = 0; i < 4; i++) {
tx = x + dx[i], ty = y + dy[i];
if (tx < 0 || ty < 0 || tx >= n || ty >= m)
continue;
if (g[tx][ty] == 'd' && g[bx][by] == 'b')
return step;
if (g[tx][ty] == '#' || g[tx][ty] == 'd')
continue;
if (tx == bx && ty == by) { // push it
ttx = tx + dx[i], tty = ty + dy[i];
if (ttx < 0 || tty < 0 || ttx >= n || tty >= m)
continue;
if (g[ttx][tty] == '#' || g[ttx][tty] == 'd')
continue;
if (dist[tx][ty][ttx][tty] == 0) {
dist[tx][ty][ttx][tty] = step + 1;
X.push(tx), Y.push(ty), BX.push(ttx), BY.push(tty);
}
} else {
if (dist[tx][ty][bx][by] == 0) {
dist[tx][ty][bx][by] = step + 1;
X.push(tx), Y.push(ty), BX.push(bx), BY.push(by);
}
}
}
}
return -1;
}
int main() {
while (scanf("%d %d", &n, &m) == 2 && n) {
for (int i = 0; i < n; i++)
scanf("%s", g[i]);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == '@')
sx = i, sy = j;
if (g[i][j] == 'd')
ex = i, ey = j;
if (g[i][j] == 'x')
bx = i, by = j;
if (g[i][j] == 'b')
cx = i, cy = j;
}
}
int ret = bfs();
if (ret < 0)
puts("No Way!");
else
printf("%d\n", ret);
}
return 0;
}
/*
3 3
d.b
.@.
x.#
3 5
...d.
.#x#.
...@b
0 0
*/