結果

問題 No.1714 Tag on Grid
コンテスト
ユーザー zkou
提出日時 2021-10-05 00:27:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 4,187 bytes
コンパイル時間 2,344 ms
コンパイル使用メモリ 207,456 KB
最終ジャッジ日時 2025-01-24 20:26:47
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 RE * 1
other AC * 7 RE * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

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

const string output[] = {"Queen can not escape and Army can not catch Queen.",
                         "Queen can escape.", "Army can catch Queen."};

void solve() {
    int H, W;
    cin >> H >> W;

    if (H * W > 1000) {
        exit(1);
    }

    // m = 0: queen moves first. m = 1: army moves first.
    auto id = [&](int qi, int qj, int ai, int aj, int m) -> int {
        return ((W * qi + qj) * H * W + (W * ai + aj)) * 2 + m;
    };

    auto id_inv = [&](int t) -> tuple<int, int, int, int, int> {
        int m = t % 2;
        t /= 2;
        int q = t / (H * W);
        int a = t % (H * W);
        int qi = q / W;
        int qj = q % W;
        int ai = a / W;
        int aj = a % W;
        return {qi, qj, ai, aj, m};
    };

    int N = H * W * H * W * 2;
    vector<vector<int>> adj_inv(N);
    vector<int> deg(N);
    vector<int> answer(N);  // 1: Yes, 0: No.
    queue<int> q;
    for (int qi = 0; qi < H; qi++) {
        for (int qj = 0; qj < W; qj++) {
            for (int ai = 0; ai < H; ai++) {
                for (int aj = 0; aj < W; aj++) {
                    for (int m = 0; m < 2; m++) {
                        int t = id(qi, qj, ai, aj, m);
                        if (qi == ai && qj == aj) {
                            answer[t] = 1;
                            q.push(t);
                        }
                        int nm = m ^ 1;
                        if (nm == 0) {
                            for (int i = 0; i < 4; i++) {
                                int di = ds[i];
                                int dj = ds[i + 1];
                                int nqi = qi + di;
                                int nqj = qj + dj;
                                if (0 <= nqi && nqi < H && 0 <= nqj &&
                                    nqj < W) {
                                    int nt = id(nqi, nqj, ai, aj, nm);
                                    adj_inv[t].push_back(nt);
                                    deg[nt]++;
                                }
                            }
                        } else {
                            for (int i = 0; i < 4; i++) {
                                int di = ds[i];
                                int dj = ds[i + 1];
                                int nai = ai + di;
                                int naj = aj + dj;
                                if (0 <= nai && nai < H && 0 <= naj &&
                                    naj < W) {
                                    int nt = id(qi, qj, nai, naj, nm);
                                    adj_inv[t].push_back(nt);
                                    deg[nt]++;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    while (!q.empty()) {
        int t = q.front();
        int m = t % 2;
        q.pop();
        // auto [e1, e2, e3, e4, e5] = id_inv(t);
        // cerr << t << ' ' << e1 << ' ' << e2 << ' ' << e3 << ' ' << e4 << ' '
        //      << e5 << ' ' << answer[t] << endl;
        for (auto &&nt : adj_inv[t]) {
            if (answer[nt] == 0) {
                // cerr << nt << endl;
                deg[nt]--;
                if (m == 1) {
                    if (answer[t] == 0) {
                        answer[nt] = 0;
                        q.push(nt);
                    } else if (answer[t] == 1 && deg[nt] == 0) {
                        answer[nt] = 1;
                        q.push(nt);
                    }
                } else {
                    if (answer[t] == 1) {
                        answer[nt] = 1;
                        q.push(nt);
                    } else if (answer[t] == 0 && deg[nt] == 0) {
                        answer[nt] = 0;
                        q.push(nt);
                    }
                }
            }
        }
    }

    int sqi, sqj, sai, saj;
    cin >> sai >> saj;
    cin >> sqi >> sqj;

    sai--;
    saj--;
    sqi--;
    sqj--;

    cout << (answer[id(sqi, sqj, sai, saj, 1)] ? "Yes" : "No") << endl;

    return;
}

int main() { solve(); }
0