UVa810 - A Dicey Problem

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
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int D[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
const int N = 15;
char str[25];
int n, m, sx, sy, u, f, to[7][7], g[N][N];
int vis[N][N][7][7];

struct State {
    int x, y, u, f;
    int pre;
    State() {}
    State(int x, int y, int u, int f, int pre) {
        this->x = x;
        this->y = y;
        this->u = u;
        this->f = f;
        this->pre = pre;
    }
} Q[10005];

void tra(int &vu, int &vf, int d) {
    if (d == 0) {int tmp = vf; vf = 7 - vu; vu = tmp;}
    if (d == 1) {int tmp = vu; vu = 7 - vf; vf = tmp;}
    if (d == 2) vu = 7 - to[vu][vf];
    if (d == 3) vu = to[vu][vf];
}

#define MP(a,b) make_pair(a,b)
typedef pair<int, int> pii;
vector<pii> ans;

void print(int u) {
    if (u == -1) return;
    print(Q[u].pre);
    ans.push_back(MP(Q[u].x, Q[u].y));
}

void bfs() {
    ans.clear();
    int head = 0, rear = 0;
    Q[rear++] = State(sx, sy, u, f, -1);
    memset(vis, 0, sizeof(vis));
    vis[sx][sy][u][f] = 1;
    while (head < rear) {
        State u = Q[head++];
        for (int i = 0; i < 4; i++) {
            State v = u;
            v.x += D[i][0];
            v.y += D[i][1];
            if (v.x <= 0 || v.x > n || v.y <= 0 || v.y > m) continue;
            if (g[v.x][v.y] != -1 && u.u != g[v.x][v.y]) continue;
            if (v.x == sx && v.y == sy) {
                print(head - 1);
                ans.push_back(MP(sx, sy));
                int tot = ans.size();
                for (int i = 0; i < tot; i++) {
                    if (i % 9 == 0) printf("n  ");
                    printf("(%d,%d)%c", ans[i].first, ans[i].second, i == tot - 1 ? 'n' : ',');
                }
                return;
            }
            tra(v.u, v.f, i);
            if (vis[v.x][v.y][v.u][v.f]) continue;
            vis[v.x][v.y][v.u][v.f] = 1;
            v.pre = head - 1;
            Q[rear++] = v;
        }
    }
    printf("n  No Solution Possiblen");
}

int main() {
    to[1][2] = 4; to[1][3] = 2; to[1][4] = 5; to[1][5] = 3;
    to[2][1] = 3; to[2][3] = 6; to[2][4] = 1; to[2][6] = 4;
    to[3][1] = 5; to[3][2] = 1; to[3][5] = 6; to[3][6] = 2;
    to[4][1] = 2; to[4][2] = 6; to[4][5] = 1; to[4][6] = 5;
    to[5][1] = 4; to[5][3] = 1; to[5][4] = 6; to[5][6] = 3;
    to[6][2] = 3; to[6][3] = 5; to[6][4] = 2; to[6][5] = 4;
    while (~scanf("%s", str) && strcmp(str, "END")) {
        printf("%s", str);
        scanf("%d%d%d%d%d%d", &n, &m, &sx, &sy, &u, &f);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &g[i][j]);
        bfs();
    }
    return 0;
}