解題區/解題區 - UVa

UVa 11501 - Laurel Creek

contents

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

Problem

在淹水的平台上，有不少樹樁 (stump) 和漂浮的圓木 (log)，可以經由圓木到另一個樹樁，請問最少要幾個操作才能從起點樹樁到終點樹樁。

操作：

  • 根據相鄰的圓木，移動到下一個樹樁。
  • 撿起某一個方向的相鄰圓木，身上最多拿著一個圓木。
  • 往另一個方向放置圓木，並且另一端要恰好接著樹樁。

給定的圓木會有多個 | 或者是 - 連接在一起表示同一個圓木。

Sample Input

1
2
3
4
5
6
7
8
9
1
7 11
....S......
....|......
B---S......
...........
...........
...........
....S.S...E

Sample Output

1
10

Solution

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
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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
int n, m;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
struct state {
    char g[17][17];
    int x, y, log;
    bool operator<(const state &a) const {
        if (x != a.x)	return x < a.x;
        if (y != a.y)	return y < a.y;
        if (log != a.log)	return log < a.log;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (g[i][j] != a.g[i][j])
                    return g[i][j] < a.g[i][j];
        return false;
    }
    void print() {
        for (int i = 0; i < n; i++, puts("")) {
            for (int j = 0; j < m; j++) {
                if (i == x && j == y)	printf("!");
                else	printf("%c", g[i][j]);
            }
        }
        printf("log %d\n", log);
        puts("--");
    }
};
int isValid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
int bfs(state init) {
    state u, v;
    queue<state> Q;
    map<state, int> R;
    int tx, ty;
    Q.push(init), R[init] = 0;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        int step = R[u];
        if (u.g[u.x][u.y] == 'E')
            return step;	
//		u.print(), getchar();
        for (int i = 0; i < 4; i++) { // traverse
            tx = u.x + dx[i], ty = u.y + dy[i];
            while (isValid(tx, ty) && u.g[tx][ty] != '.') {
                if (u.g[tx][ty] == 'S' || u.g[tx][ty] == 'B' || u.g[tx][ty] == 'E') {
                    v = u, v.x = tx, v.y = ty;
                    if (R.find(v) == R.end()) {
                        R[v] = step + 1;
                        Q.push(v);
                    }
                    break;
                }
                if (i < 2 && u.g[tx][ty] != '-')	break;
                if (i > 1 && u.g[tx][ty] != '|')	break;
                tx += dx[i], ty += dy[i];
            }
        }
        if (u.log == 0) { // pick up
            for (int i = 0; i < 4; i++) {
                tx = u.x + dx[i], ty = u.y + dy[i];
                if (isValid(tx, ty) && ((i < 2 && u.g[tx][ty] == '-') || (i > 1 && u.g[tx][ty] == '|'))) {
                    v = u;
                    while (isValid(tx, ty) && u.g[tx][ty] != '.') {
                        if (u.g[tx][ty] == 'S' || u.g[tx][ty] == 'B' || u.g[tx][ty] == 'E') {
                            if (R.find(v) == R.end()) {
                                R[v] = step + 1;
                                Q.push(v);
                            }
                            break;
                        }
                        v.g[tx][ty] = '.', v.log++;
                        if (i < 2 && u.g[tx][ty] != '-')	break;
                        if (i > 1 && u.g[tx][ty] != '|')	break;
                        tx += dx[i], ty += dy[i];						
                    }
                }
            }
        } else { // put down.
            for (int i = 0; i < 4; i++) {
                tx = u.x + dx[i], ty = u.y + dy[i];
                if (isValid(tx, ty) && u.g[tx][ty] == '.') {
                    int dist = 0;
                    while (isValid(tx, ty)) {
                        if (u.g[tx][ty] == 'S' || u.g[tx][ty] == 'B' || u.g[tx][ty] == 'E') {
                            v = u;
                            if (dist == u.log) {
                                v.log = 0;
                                tx = u.x + dx[i], ty = u.y + dy[i];
                                while (isValid(tx, ty) && u.g[tx][ty] == '.') {
                                    if (u.g[tx][ty] == 'S' || u.g[tx][ty] == 'B' || u.g[tx][ty] == 'E')
                                        break;
                                    if (i < 2)	v.g[tx][ty] = '-';
                                    if (i > 1)	v.g[tx][ty] = '|';
                                    tx += dx[i], ty += dy[i];
                                }
                                if (R.find(v) == R.end()) {
                                    R[v] = step + 1;
                                    Q.push(v);
                                }
                            }
                            break;
                        }
                        if (u.g[tx][ty] != '.')	break;
                        dist++;
                        tx += dx[i], ty += dy[i];
                    }
                }
            }
        }
    }
    return 0;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        state init, u, v;
        for (int i = 0; i < n; i++)
            scanf("%s", init.g[i]);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (init.g[i][j] == 'B')
                    init.x = i, init.y = j, init.log = 0;
            }
        }
        int ret = bfs(init);
        printf("%d\n", ret);
    }
    return 0;
}
/*
999
7 11
....S......
....|......
B---S......
...........
...........
...........
....S.S...E
4 4
....
.B.S
.|..
...E
7 11
....S...S..
........|..
B-----S.|.E
......|.|..
......|.S..
......|....
....S-S....
4 4
....
S-B.
....
..E.
*/