解題區/解題區 - UVa

UVa 12607 - Amazing Maze

contents

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

Problem

在一個迷宮中有 M x N 個房間，每個房間有四個門，並且以逆時針的順序依次出現，每一個時間每個房間只會有一個門通往另一個地方。

必須從左上角開始，花最少時間收集到 K 個寶物後抵達右下角。

Sample Input

1
2
3
4
5
6
2 2
EE
NN
1
1 2
0 0

Sample Output

1
2

Solution

分析狀態，由於 K 不大，直接 2^K 狀態下去，而只會有四個門，因此時間論替只需要考慮 mod 4 的結果，最後 dist[x][y][4][1<<8] 抵達 (x, y) 時的門狀態、同時身上帶了多少寶物 (用 bitmask 去壓縮)。

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
#include <stdio.h> 
#include <algorithm>
#include <queue>
#include <assert.h>
using namespace std;
const int dx[] = {-1, 0, 1, 0}; // N E S W 
const int dy[] = {0, 1, 0, -1};
int used[100][100][4][1<<8] = {}, testcase = 0;
int dist[100][100][4][1<<8] = {};
int main() {
    int N, M, K, x, y;
    char g[128][128];
    while (scanf("%d %d", &N, &M) == 2 && N+M) {
        int treasure[128][128] = {}, dirg[128][128] = {};
        for (int i = 0; i < N; i++) {
            scanf("%s", g[i]);
            for (int j = 0; j < M; j++) {
                if (g[i][j] == 'N')
                    dirg[i][j] = 0;			
                if (g[i][j] == 'E')
                    dirg[i][j] = 1;	
                if (g[i][j] == 'S')
                    dirg[i][j] = 2;	
                if (g[i][j] == 'W')
                    dirg[i][j] = 3;
            }
        }
        scanf("%d", &K);
        for (int i = 0; i < K; i++) {
            scanf("%d %d", &x, &y);
            x--, y--;
            assert(treasure[x][y] == 0);
            treasure[x][y] = i + 1;
        }
        queue<int> X, Y, D, T;
        int x = 0, y = 0, d = 0, t = 0;
        int tx, ty, td, tt;
        if (treasure[x][y])
            t |= 1<<(treasure[x][y] - 1);
        X.push(x), Y.push(y), D.push(d), T.push(t);
        testcase++;
        used[x][y][d][t] = testcase;
        dist[x][y][d][t] = 0;
        while (!X.empty()) {
            x = X.front(), X.pop();
            y = Y.front(), Y.pop();
            d = D.front(), D.pop();
            t = T.front(), T.pop();	
                    
            tx = x, ty = y, td = (d + 1)%4, tt = t;
            if (used[tx][ty][td][tt] != testcase) {
                used[tx][ty][td][tt] = testcase;
                dist[tx][ty][td][tt] = dist[x][y][d][t] + 1;
                X.push(tx), Y.push(ty), D.push(td), T.push(tt);
                if (tx == N - 1 && ty == M - 1 && tt == (1<<K) - 1)
                    break;
            }
            
            int dir = (dirg[x][y] + d)%4;
            tx = x + dx[dir], ty = y + dy[dir], td = (d + 1)%4, tt = t;
            if (tx < 0 || ty < 0 || tx >= N || ty >= M)
                continue;
            if (treasure[tx][ty])
                tt |= 1<<(treasure[tx][ty] - 1);
            if (used[tx][ty][td][tt] != testcase) {
                used[tx][ty][td][tt] = testcase;
                dist[tx][ty][td][tt] = dist[x][y][d][t] + 1;
                X.push(tx), Y.push(ty), D.push(td), T.push(tt);
                if (tx == N - 1 && ty == M - 1 && tt == (1<<K) - 1)
                    break;
            }
        }
        int ret = 0x3f3f3f3f;
        for (int i = 0; i < 4; i++) {
            if (used[N-1][M-1][i][(1<<K)-1] == testcase)
                ret = min(ret, dist[N-1][M-1][i][(1<<K)-1]);
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
2 2
EE
NN
1
1 2
1 1
E
1
1 1
1 2
NE
1
1 2
0 0
*/