AOJ 2702 Alternate Escape

解法

後退解析で解く.
ゲームの探索なので,最初は始点からDFSしたくなるかもしれないが,普通に状態が自分に戻ってくるような遷移があるので困る.
こういうときは確定しているところから探索を始めて,始点に戻ってこれるか,みたいに考える.
最初,Alice が勝つことができる位置は,端で,壁の状態がどちらでもゴールできるような位置である.
これを queue なりなんなりに入れて管理しておき,そこから遷移できるところの勝利フラグを立てていく.
以降は勝利フラグが壁の状態によらず立っている場合に,新たに勝利確定状態として queue に突っ込む.
探索が終わったときに (r, c) の勝利確定フラグを確認して終わり.
計算量は O(wh).

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

template<typename T>
std::vector<T> table(int n, T v) { return std::vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return std::vector<decltype(val)>(n, std::move(val));
}

int main() {
    int h, w, r, c;
    while(cin >> h >> w >> r >> c, h) {
        r--; c--;
        vector<vector<int>> horz(h + 1, vector<int>(w)), vert(h, vector<int>(w + 1));
        for(int i = 0; i < 2 * h + 1; ++i) {
            if(i & 1) {
                for(int j = 0; j < w + 1; ++j) {
                    cin >> vert[i / 2][j];
                }
            } else {
                for(int j = 0; j < w; ++j) {
                    cin >> horz[i / 2][j];
                }
            }
        }
        auto win = table(h, w, 2, -1); // 1: alice, 0: bob, -1: ?
        queue<tuple<int, int, int>> que;
        for(int i = 0; i < h; ++i) {
            win[i][0][vert[i][0]] = win[i][w - 1][vert[i][w]] = 1;
        }
        for(int i = 0; i < w; ++i) {
            win[0][i][horz[0][i]] = win[h - 1][i][horz[h][i]] = 1;
        }
        for(int i = 0; i < h; ++i) {
            if(win[i][0][0] == 1 && win[i][0][1] == 1) {
                que.emplace(i, 0, 0);
                que.emplace(i, 0, 1);
            }
        }
        for(int i = 0; i < w; ++i) {
            if(win[0][i][0] == 1 && win[0][i][1] == 1) {
                que.emplace(0, i, 0);
                que.emplace(0, i, 1);
            }
        }

        constexpr int dx[4] = {0, 1, 0, -1};
        constexpr int dy[4] = {1, 0, -1, 0};
        auto in_range = [&] (int y, int x) {
            return 0 <= y && y < h && 0 <= x && x < w;
        };
        auto check_wall = [&] (int y, int x, int dir, int f) {
            if(dir & 1) { // move x
                return vert[y][x + (dir == 1)] == f;
            } else {
                return horz[y + (dir == 0)][x] == f;
            }
        };
        while(!que.empty()) {
            int y, x, f;
            tie(y, x, f) = que.front();
            que.pop();
            for(int i = 0; i < 4; ++i) {
                int ny = y + dy[i], nx = x + dx[i];
                if(!in_range(ny, nx)) continue;
                for(int nf = 0; nf < 2; ++nf) {
                    if(check_wall(y, x, i, nf) && win[ny][nx][nf] == -1) {
                        win[ny][nx][nf] = 1;
                        if(win[ny][nx][!nf] == 1) {
                            que.emplace(ny, nx, 0);
                            que.emplace(ny, nx, 1);
                        }
                    }
                }
            }
        }

        if(win[r][c][0] == 1) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}

感想

昔問題で出されて,その時は解けなかった気がする.