#1173095 (C++23) No.3598 Queen vs. King

• 問題: No.3598 Queen vs. King
• ユーザー: tkdgkb
• 提出日時: 2026-07-24 21:59:49
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 176 ms / 2,000 ms
• コード長: 4,163 bytes
• コンパイル時間: 2,592 ms
• コンパイル使用メモリ: 360,544 KB
• 実行使用メモリ: 6,016 KB
• 平均クエリ数: 2049.33
• 最終ジャッジ日時: 2026-07-24 22:00:57
• 合計ジャッジ時間: 4,501 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 2
other	AC * 10

ソースコード

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

#pragma GCC optimize("O3,unroll-loops")

int H, W;

struct State {
    int qx, qy, kx, ky, t;
    bool operator==(const State& o) const {
        return qx == o.qx && qy == o.qy && kx == o.kx && ky == o.ky && t == o.t;
    }
};

struct Hash {
    size_t operator()(const State& s) const {
        return (s.qx * 131313) ^ (s.qy * 1313) ^ (s.kx * 13) ^ s.ky ^ (s.t * 7);
    }
};

unordered_map<State, bool, Hash> memo_bob;
unordered_set<State, Hash> memo_alice_false;

bool bob_lose(int qx, int qy, int kx, int ky, int turns_left);

bool alice_win(int qx, int qy, int kx, int ky, int turns_left, pair<int,int>& out_move) {
    if (turns_left == 0) return false;
    State st = {qx, qy, kx, ky, turns_left};
    if (memo_alice_false.count(st)) return false;

    vector<pair<int, int>> moves;
    moves.reserve(H + W + 2 * max(H, W));
    
    auto add = [&](int r, int c) {
        if (r >= 1 && r <= H && c >= 1 && c <= W) {
            if (!(r == kx && c == ky)) moves.push_back({r, c});
        }
    };
    
    for (int c = 1; c <= W; ++c) if (c != qy) add(qx, c);
    for (int r = 1; r <= H; ++r) if (r != qx) add(r, qy);
    for (int d = 1; d <= max(H, W); ++d) {
        if (qx + d <= H && qy + d <= W) add(qx + d, qy + d);
        if (qx - d >= 1 && qy - d >= 1) add(qx - d, qy - d);
        if (qx + d <= H && qy - d >= 1) add(qx + d, qy - d);
        if (qx - d >= 1 && qy + d <= W) add(qx - d, qy + d);
    }

    auto score = [&](pair<int,int> m) {
        int val = max(abs(m.first - kx), abs(m.second - ky));
        if (m.first == H - 1 && m.second == W - 1) val -= 10000;
        else if (m.first == H - 2 && m.second == W - 2) val -= 5000;
        else if (m.first == H - 2 && m.second == 1) val -= 1000;
        else if (m.first == 1 && m.second == W - 2) val -= 1000;
        return val;
    };

    sort(moves.begin(), moves.end(), [&](auto& a, auto& b) {
        return score(a) < score(b);
    });

    for (auto& m : moves) {
        if (bob_lose(m.first, m.second, kx, ky, turns_left)) {
            out_move = m;
            return true;
        }
    }
    memo_alice_false.insert(st);
    return false;
}

bool bob_lose(int qx, int qy, int kx, int ky, int turns_left) {
    State st = {qx, qy, kx, ky, turns_left};
    if (memo_bob.count(st)) return memo_bob[st];

    vector<pair<int, int>> moves;
    for (int dx = -1; dx <= 1; ++dx) {
        for (int dy = -1; dy <= 1; ++dy) {
            if (dx == 0 && dy == 0) continue;
            int nx = kx + dx, ny = ky + dy;
            if (nx >= 1 && nx <= H && ny >= 1 && ny <= W) {
                if (nx == qx || ny == qy || abs(nx - qx) == abs(ny - qy)) continue;
                moves.push_back({nx, ny});
            }
        }
    }
    
    if (moves.empty()) return memo_bob[st] = true;
    if (turns_left == 1) return memo_bob[st] = false;

    for (auto& m : moves) {
        pair<int,int> dummy;
        if (!alice_win(qx, qy, m.first, m.second, turns_left - 1, dummy)) {
            return memo_bob[st] = false;
        }
    }
    return memo_bob[st] = true;
}

void solve() {
    int T;
    if (!(cin >> T)) return;
    while (T--) {
        cin >> H >> W;
        int qx = 1, qy = 1;
        memo_bob.clear();
        memo_alice_false.clear();
        
        int turn = 1;
        while (true) {
            int kx, ky;
            cin >> kx >> ky;
            if (kx == 0 && ky == 0) break;
            if (kx == -1 && ky == -1) exit(0);

            int turns_left = 4 - turn;
            if (turns_left <= 0) turns_left = 1;

            pair<int, int> best_m = {-1, -1};
            if (!alice_win(qx, qy, kx, ky, turns_left, best_m)) {
                best_m = {qx < H ? qx + 1 : qx - 1, qy};
                if (best_m.first == kx && best_m.second == ky) {
                    best_m.second = qy < W ? qy + 1 : qy - 1;
                }
            }

            cout << best_m.first << " " << best_m.second << endl;
            qx = best_m.first;
            qy = best_m.second;
            turn++;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}