Codeforces Round #354 (Div. 2) D. Theseus and labyrinth

Div2 だけど久しぶりにこどふぉやった気がする・・・

問題

codeforces.com

迷路が与えられる。迷路はセルが H*W 個あるような形をしており, 各セルにはいくつかの方向にドアがついている(上, 右, 下, 左 からいくつか)。
あるセルからは, 隣接するセルに移動することができるが, その際は

• セルから出る方向にドアがある
• 次に入ろうとしているセルに, 入ろうとしている方向にドアがある

という条件を満たしていなければならない。

迷路に入った人は,

• 条件を満たす隣のセルに移動する(1 分かかる)
• 全てのセルを時計方向に回転させる(1 分かかる)

のいずれかの操作を何回も行うことができる。出発地点から目標地点に行くのにかかる最小時間を求めよ。

解法

ダイクストラやるだけ。解いてるとき筋肉マッチョ大工さんを思い浮かべていました。

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};

string board[1010];
int door[1010][1010];

int dp[4*1001000];

int n, m;
inline int getVertex(int rotate, int r, int c) {
    return rotate*n*m+r*m+c;
}
inline pii getXY(int state) {
    state %= n*m;
    return pii(state/m, state%m);
}
inline int getState(int state, int rot) {
    int ret = 0;
    for (int i = 0; i < 4; i++) {
        if ((state>>i)&1) {
            ret |= 1<<((i+4-rot)%4);
        }
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> board[i];
    map<char, int> corr;
    const int RIGHT = 1, UP = 2, LEFT = 4, DOWN = 8;
    corr['+'] = RIGHT+UP+LEFT+DOWN;
    corr['-'] = RIGHT+LEFT;
    corr['|'] = UP+DOWN;
    corr['^'] = UP;
    corr['>'] = RIGHT;
    corr['<'] = LEFT;
    corr['v'] = DOWN;
    corr['L'] = corr['+'] - LEFT;
    corr['R'] = corr['+'] - RIGHT;
    corr['U'] = corr['+'] - UP;
    corr['D'] = corr['+'] - DOWN;
    corr['*'] = 0;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
        door[i][j] = corr[board[i][j]];
    }
    int xt, yt, xm, ym;
    cin >> yt >> xt;
    cin >> ym >> xm;
    --yt; --xt; --ym; --xm;
    const int INF = 1<<30;
    for (int i = 0; i < 4*n*m; i++)
        dp[i] = INF;
    dp[getVertex(0, yt, xt)] = 0;
    priority_queue<pii> que;
    que.push(pii(0, getVertex(0, yt, xt)));
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int u = p.second;
        int dist = -p.first;
        if (dist > dp[u]) continue;
        // 回転
        int rot = u/(n*m);
        auto xy = getXY(u);
        {
            int tmp = getVertex((rot+1)%4, xy.first, xy.second);
            if (dp[tmp] > dist+1) {
                dp[tmp] = dist+1;
                que.push(make_pair(-dp[tmp], tmp));
            }
        }
        // 移動
        int state = getState(door[xy.first][xy.second], rot);
        for (int i = 0; i < 4; i++) {
            if (((state>>i)&1) == 0) continue;
            int ny = xy.first+dy[i], nx = xy.second+dx[i];
            if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
            int nstate = getState(door[ny][nx], rot);
            int ni = (i+2)%4;
            if (((nstate>>ni)&1) == 0) continue;
            int tmp = getVertex(rot, ny, nx);
            if (dp[tmp] > dist+1) {
                dp[tmp] = dist+1;
                que.push(make_pair(-dp[tmp], tmp));
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < 4; i++) {
        ans = min(ans, dp[getVertex(i, ym, xm)]);
    }
    if (ans >= INF) ans = -1;
    cout << ans << endl;
    return 0;
}