結果

問題 No.1714 Tag on Grid
ユーザー zkouzkou
提出日時 2021-10-05 00:27:59
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 4,187 bytes
コンパイル時間 3,263 ms
コンパイル使用メモリ 214,308 KB
実行使用メモリ 16,184 KB
最終ジャッジ日時 2023-10-24 11:30:16
合計ジャッジ時間 4,881 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 RE -
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 AC 10 ms
5,956 KB
testcase_09 AC 48 ms
16,184 KB
testcase_10 AC 13 ms
7,012 KB
testcase_11 AC 13 ms
7,012 KB
testcase_12 AC 4 ms
4,348 KB
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
権限があれば一括ダウンロードができます

ソースコード

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