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; } } }
感想
昔問題で出されて,その時は解けなかった気がする.