サイコロを転がさないで [Kyoto University Programming Contest 2020 Spring B]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/B

解説

到達可能性といえばBFS。BFSだろうなぁと思って考えていくと解ける。 状態は(x座標, y座標, サイコロの下の面の数字, サイコロの右の面の数字)で表現する。 遷移は4方向なので、BFSしても間に合う。

サイコロについては、真面目にサイコロクラスを作ってBFSをした。満足。 …と思ったらMLE！ 泣く泣く、queueに突っ込むのはサイコロの数字だけにして、 サイコロクラスのインスタンスはキャッシュに突っ込んで使いまわしたらAC。

//              v back
//          .-------.
//         /  up   /|
//        /_______/ |
// left > |       | | < right
//        | front | /
//        |       |/
//        '-------'
//            ^ down
struct Dice {
    int up, down, left, right, front, back;
    Dice() {}
    Dice(int up, int down, int left, int right, int front, int back) : up(up), down(down), left(left), right(right), front(front), back(back) {}
};
Dice rotateToLeft(Dice from) { return Dice(from.right, from.left, from.up, from.down, from.front, from.back); }
Dice rotateToRight(Dice from) { return rotateToLeft(rotateToLeft(rotateToLeft(from))); }
Dice rotateToFront(Dice from) { return Dice(from.back, from.front, from.left, from.right, from.up, from.down); }
Dice rotateToBack(Dice from) { return rotateToFront(rotateToFront(rotateToFront(from))); }
Dice rotateByDxdy(Dice from, int dxdy) {
    if (dxdy == 0) return rotateToBack(from);
    else if (dxdy == 1) return rotateToRight(from);
    else if (dxdy == 2) return rotateToFront(from);
    else return rotateToLeft(from);
}

int H, W;
string S[100];
//---------------------------------------------------------------------------------------------------
bool vis[100][100][7][7];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
Dice cache[7][7];
#define yes "YES"
#define no "NO"
string solve() {
    Dice initialDice(1, 6, 4, 3, 2, 5);

    queue<pair<int, int>> que;
    vis[0][0][initialDice.down][initialDice.right] = true;
    cache[initialDice.down][initialDice.right] = initialDice;
    que.push({ 0, initialDice.down * 10 + initialDice.right });

    while (!que.empty()) {
        auto q = que.front(); que.pop();

        int x = q.first % 100;
        int y = q.first / 100;
        int downValue = q.second / 10;
        int rightValue = q.second % 10;
        auto dice = cache[downValue][rightValue];

        if (y == H - 1 && x == W - 1) return yes;

        rep(d, 0, 4) {
            int xx = x + dx[d];
            int yy = y + dy[d];
            if (0 <= xx && xx < W && 0 <= yy && yy < H) {
                auto dice2 = rotateByDxdy(dice, d);
                cache[dice2.down][dice2.right] = dice2;
                if (S[yy][xx] - '0' == dice2.down && !vis[yy][xx][dice2.down][dice2.right]) {
                    vis[yy][xx][dice2.down][dice2.right] = true;
                    que.push({ yy * 100 + xx, dice2.down * 10 + dice2.right });
                }
            }
        }
    }

    return no;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> S[y];
    cout << solve() << endl;
}