解題區/解題區 - UVa

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
*/