解題區/解題區 - UVa

UVa 810 - A Dicey Problem

contents

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

Problem

給一個 2D 地圖，上面放置一骰子，人從 2D 地圖的下方往上方看，骰子必須貼著某一條邊，往上下左右的地方滾過去，滾的時候必須滿足，其骰子上方的點數與地圖該格的點數相同，或者是移動到星號位置。

一開始給定骰子面向玩家的點數、以及骰子上方的點數，骰子滾動出去回到原本地方的最短路徑為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
DICEMAZE1
3 3 1 2 5 1
-1 2 4
5 5 6
6 -1 -1
DICEMAZE2
4 7 2 6 3 6
6 4 6 0 2 6 4
1 2 -1 5 3 6 1
5 3 4 5 6 4 2
4 1 2 0 3 -1 6
DICEMAZE3
3 3 1 1 2 4
2 2 3
4 5 6
-1 -1 -1
END

Sample Output

1
2
3
4
5
6
7
8
DICEMAZE1
  (1,2),(2,2),(2,3),(3,3),(3,2),(3,1),(2,1),(1,1),(1,2)
DICEMAZE2
  (2,6),(2,5),(2,4),(2,3),(2,2),(3,2),(4,2),(4,1),(3,1),
  (2,1),(2,2),(2,3),(2,4),(2,5),(1,5),(1,6),(1,7),(2,7),
  (3,7),(4,7),(4,6),(3,6),(2,6)
DICEMAZE3
  No Solution Possible

Solution

每一個 2D 位置 (x, y) 會有兩個骰子資訊做為紀錄，只需要知道骰子的兩個面，即可知道骰子的結構。

針對其狀態進行 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
#include <stdio.h>
#include <string.h> 
#include <queue>
#include <vector>
#include <assert.h>
using namespace std;
#define MAXSTATE 65536
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
struct state {
    int x, y, top, front;
    state *prev;
} states[MAXSTATE];
int statesIdx;
int n, m, sx, sy, dtop, dfront;
int g[32][32];
state* getNewState(int x, int y, int dtop, int dfront, state *prev = NULL) {
    state *p = &states[statesIdx++];
    assert (statesIdx < MAXSTATE);
    p->x = x, p->y = y, p->top = dtop, p->front = dfront, p->prev = prev;
    return p;
}
int diceTable[7][7]; // [front][top] = right
void rotateDice(int dir, int dtop, int dfront, int &rtop, int &rfront) {
    rtop = rfront = 1;
    if (dir == 0) { // roll up
        rtop = dfront, rfront = 7 - dtop;
    } else if (dir == 1) { // roll down
        rtop = 7 - dfront, rfront = dtop;
    } else if (dir == 2) { // roll left
        rfront = dfront;
        rtop = diceTable[dfront][dtop];
    } else if (dir == 3) { // roll right
        rfront = dfront;
        rtop = 7 - diceTable[dfront][dtop];
    }
}
void bfs(int sx, int sy, int dtop, int dfront) {
    statesIdx = 0;
    int used[32][32][7][7] = {}; // used[x][y][dtop][dfront]
    int tx, ty, tdtop, tdfront;
    queue<state*> Q;
    state *u, *v;
    Q.push(getNewState(sx, sy, dtop, dfront));
    used[sx][sy][dtop][dfront] = 1;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        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] != -1 && g[tx][ty] != u->top)
                continue;
            if (tx == sx && ty == sy) { // back to start square, print result
                vector< pair<int, int> > ret;
                state *p = u;
                ret.push_back(make_pair(sx, sy));
                while (p != NULL) {
                    ret.push_back(make_pair(p->x, p->y));
                    p = p->prev;
                }
                for (int i = ret.size() - 1, j = 0; i >= 0; i--, j++) {
                    if (j%9 == 0)	printf("  ");
                    if (j%9 != 0)	printf(",");
                    printf("(%d,%d)", ret[i].first, ret[i].second);					if (j%9 == 8 || i == 0)	{
                        if (i)	printf(",\n");
                        else	puts("");
                    }
                }
                return ;
            }
            rotateDice(i, u->top, u->front, tdtop, tdfront);
            if (used[tx][ty][tdtop][tdfront])
                continue;
            used[tx][ty][tdtop][tdfront] = 1;
            v = getNewState(tx, ty, tdtop, tdfront, u);
            Q.push(v);
        }
    }
    puts("  No Solution Possible");
}
int main() {
    // diceface[front][top] = right
    diceTable[1][2] = 4, diceTable[1][3] = 2, diceTable[1][4] = 5, diceTable[1][5] = 3;
    diceTable[2][1] = 3, diceTable[2][3] = 6, diceTable[2][4] = 1, diceTable[2][6] = 4;
    diceTable[3][1] = 5, diceTable[3][2] = 1, diceTable[3][5] = 6, diceTable[3][6] = 2;
    diceTable[4][1] = 2, diceTable[4][2] = 6, diceTable[4][5] = 1, diceTable[4][6] = 5;
    diceTable[5][1] = 4, diceTable[5][3] = 1, diceTable[5][4] = 6, diceTable[5][6] = 3;
    diceTable[6][2] = 3, diceTable[6][3] = 5, diceTable[6][4] = 2, diceTable[6][5] = 4;
    
    char testcase[1024];
    while (scanf("%s", testcase) == 1) {
        if (!strcmp("END", testcase))
            break;
        scanf("%d %d %d %d %d %d", &n, &m, &sx, &sy, &dtop, &dfront);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &g[i][j]);
        printf("%s\n", testcase);
        bfs(sx, sy, dtop, dfront);
    }
    return 0;
}