AOJ 2172 - Queen's Case

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2172

解法

ゲームの状態グラフにループがあるので、ただ DFS やるだけだとうまくいかない。
これは後退解析という手法で解けて、ど典型なので知らなかったら覚えてしまってよい（どの問題でも同じやり方だし）。
後退解析は、勝ち負けが確定できるところから探索していく手法で、最終的に勝ち負けが確定できない状態が、引き分けになる。
ググればいい記事がたくさんあるだろうからここには書かない。

ソースコード

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

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

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));
}

enum {
    Escape,
    Caught,
    Undecided
};

int main() {
    int w, h;
    while(cin >> w >> h, w) {
        vector<string> v(h);
        for(auto& a : v) cin >> a;

        auto can_move_to = [&] (int y, int x) {
            return 0 <= y && y < h && 0 <= x && x < w && v[y][x] != '#';
        };

        int qy = -1, qx = -1, ay = -1, ax = -1;
        auto dp = table(h, w, h, w, 2, Undecided);
        auto deg = table(h, w, h, w, 2, 0);
        queue<tuple<int, int, int, int, int>> que;
        for(int i = 0; i < h; ++i) {
            for(int j = 0; j < w; ++j) {
                if(v[i][j] == '#') continue;

                if(v[i][j] == 'Q') qy = i, qx = j;
                if(v[i][j] == 'A') ay = i, ax = j;
                for(int k = 0; k < h; ++k) {
                    for(int l = 0; l < w; ++l) {
                        if(v[k][l] == '#' || (k == i && l == j)) continue;

                        for(int d = 0; d < 5; ++d) {
                            const int ny1 = i + dy[d], nx1 = j + dx[d];
                            const int ny2 = k + dy[d], nx2 = l + dx[d];
                            deg[i][j][k][l][0] += can_move_to(ny1, nx1) && v[i][j] != 'E';
                            deg[i][j][k][l][1] += can_move_to(ny2, nx2);
                        }

                        if(v[i][j] == 'E') {
                            dp[i][j][k][l][0] = Escape;
                            deg[i][j][k][l][0] = 0;
                            que.emplace(i, j, k, l, 0);
                        }
                    }
                }
                dp[i][j][i][j][0] = dp[i][j][i][j][1] = Caught;
                que.emplace(i, j, i, j, 0);
                que.emplace(i, j, i, j, 1);
            }
        }
        while(!que.empty()) {
            int qy, qx, ay, ax, turn; tie(qy, qx, ay, ax, turn) = que.front();
            que.pop();
            if(turn == 0) { // Queen's turn, so consider army's move
                for(int d = 0; d < 5; ++d) {
                    const int nay = ay + dy[d], nax = ax + dx[d];
                    if(!can_move_to(nay, nax) || dp[qy][qx][nay][nax][!turn] != Undecided) continue;
                    if(dp[qy][qx][ay][ax][turn] == Escape) {
                        if(--deg[qy][qx][nay][nax][!turn] == 0) {
                            dp[qy][qx][nay][nax][!turn] = Escape;
                            que.emplace(qy, qx, nay, nax, !turn);
                        }
                    } else {
                        deg[qy][qx][nay][nax][!turn] = 0;
                        dp[qy][qx][nay][nax][!turn] = Caught;
                        que.emplace(qy, qx, nay, nax, !turn);
                    }
                }
            } else {
                for(int d = 0; d < 5; ++d) {
                    const int nqy = qy + dy[d], nqx = qx + dx[d];
                    if(!can_move_to(nqy, nqx) || dp[nqy][nqx][ay][ax][!turn] != Undecided) continue;
                    if(dp[qy][qx][ay][ax][turn] == Escape) {
                        deg[nqy][nqx][ay][ax][!turn] = 0;
                        dp[nqy][nqx][ay][ax][!turn] = Escape;
                        que.emplace(nqy, nqx, ay, ax, !turn);
                    } else {
                        if(--deg[nqy][nqx][ay][ax][!turn] == 0) {
                            dp[nqy][nqx][ay][ax][!turn] = Caught;
                            que.emplace(nqy, nqx, ay, ax, !turn);
                        }
                    }
                }
            }
        }

        const auto ans = dp[qy][qx][ay][ax][0];
        if(ans == Escape) {
            cout << "Queen can escape." << endl;
        } else if(ans == Caught) {
            cout << "Army can catch Queen." << endl;
        } else {
            cout << "Queen can not escape and Army can not catch Queen." << endl;
        }
    }
}

感想

Caught になってるときに間違えて引き分けの出力しててサンプルが合わず無限に悩んでた（目がついてないね