UVa 10381 - The Rock

contents

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

Problem

給定一個 N x M 地圖,已知有部分的牆壁和一個透明的牆壁,每一個障礙物都佔據一個方格,而透明牆壁一開始不知道位於何處,直到碰壁的時候才發現,找一條最慘情況下的最短路徑。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
8 8
..X.....
........
##.##...
........
##.##...
##.##...
........
..E.....
3 4
..X.
.##.
.E..

Sample Output

1
2
15
11

Solution

最小化最大值,首先窮舉任何一個透明牆壁可能出現的地方,對於透明牆壁的鄰近四格建立再碰壁方向下,抵達終點的最短路徑。

接著,使用最短路的方式進行更新,在這裡使用 dijkstra 的方式,對於每一個點的狀態為 (走到這裡第幾步) = 從起點走到這,最慘的偏移路徑最小化 為何。

概念上理解,設計一條路徑,路徑畫好後,對於每一點賭下一個點就是透明牆壁,偏移路徑長最長為何就會是該路徑的花費。

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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <assert.h>
#include <algorithm>
using namespace std;
char g[64][64];
int dist[64][64], walldist[64][64][4];
int n, m;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
struct State {
int x, y;
int g, h;
State(int a=0, int b=0, int c=0, int d=0):
x(a), y(b), g(c), h(d) {}
bool operator<(const State &a) const {
return h > a.h;
}
};
int dp[40][40][40 * 40];
int search(int sx, int sy, int ex, int ey) {
priority_queue<State> pQ;
State u, v;
int tx, ty, h;
pQ.push(State(sx, sy, 0, 0));
memset(dp, 63, sizeof(dp));
while (!pQ.empty()) {
u = pQ.top(), pQ.pop();
if (u.h > dp[u.x][u.y][u.g])
continue;
if (u.x == ex && u.y == ey)
return u.h;
for (int i = 0; i < 4; i++) {
tx = u.x + dx[i], ty = u.y + dy[i];
if (tx < 0 || ty < 0 || tx >= n || ty >= m)
continue;
if (g[tx][ty] == '#' || g[tx][ty] == 'E')
continue;
if (g[tx][ty] == '.')
h = max(u.h, u.g + walldist[u.x][u.y][i]);
else if (g[tx][ty] == 'X')
h = max(u.h, u.g);
assert(u.g + 1 < 40 * 40);
if (dp[tx][ty][u.g + 1] > h) {
dp[tx][ty][u.g + 1] = h;
pQ.push(State(tx, ty, u.g + 1, h));
}
}
}
return 0;
}
void bfs(int sx, int sy) {
memset(dist, 63, sizeof(dist));
queue<int> X, Y;
int tx, ty;
X.push(sx), Y.push(sy);
dist[sx][sy] = 0;
while (!X.empty()) {
sx = X.front(), X.pop();
sy = Y.front(), Y.pop();
for (int i = 0; i < 4; i++) {
tx = sx + dx[i], ty = sy + dy[i];
if (tx < 0 || ty < 0 || tx >= n || ty >= m)
continue;
if (g[tx][ty] == '#' || dist[tx][ty] <= dist[sx][sy] + 1)
continue;
dist[tx][ty] = dist[sx][sy] + 1;
X.push(tx), Y.push(ty);
}
}
}
int main() {
int testcase;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++)
scanf("%s", g[i]);
int sx, sy, ex, ey, tx, ty;
memset(walldist, 0, sizeof(walldist));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == 'E') sx = i, sy = j;
if (g[i][j] == 'X') ex = i, ey = j;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] != '.')
continue;
g[i][j] = '#';
bfs(ex, ey);
for (int k = 0; k < 4; k++) {
tx = i + dx[k], ty = j + dy[k];
if (tx < 0 || ty < 0 || tx >= n || ty >= m)
continue;
if (g[tx][ty] == '#')
continue;
walldist[tx][ty][(k+2)%4] = dist[tx][ty];
}
g[i][j] = '.';
}
}
int ret = search(sx, sy, ex, ey);
printf("%d\n", ret);
}
return 0;
}
/*
2
8 8
..X.....
........
##.##...
........
##.##...
##.##...
........
..E.....
3 4
..X.
.##.
.E..
*/