#1173278 (C++23) No.3599 Queen Moving Query

• 問題: No.3599 Queen Moving Query
• ユーザー: shingo0909
• 提出日時: 2026-07-24 22:54:23
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: WA
• 実行時間: -
• コード長: 6,048 bytes
• コンパイル時間: 2,453 ms
• コンパイル使用メモリ: 356,596 KB
• 実行使用メモリ: 523,776 KB
• 最終ジャッジ日時: 2026-07-24 22:54:53
• 合計ジャッジ時間: 16,204 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_1

ファイルパターン	結果
sample	AC * 2
other	AC * 25 WA * 1

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

struct SSSP {
  private:
    struct Edge {
        int to;
        ll cost;
    };

    int n;
    vector<vector<Edge>> adj;
    vector<ll> d;
    vector<int> prev_node;
    static constexpr ll INF = 1LL << 62;

  public:
    explicit SSSP(int n) : n(n), adj(n) {}

    void add_edge(int from, int to, ll cost = 1) {
        adj[from].push_back({to, cost});
    }

    void reset() {
        d.assign(n, INF);
        prev_node.assign(n, -1);
    }
    // BFS
    void bfs(int s) {
        reset();
        queue<int> q;
        d[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto &e : adj[v]) {
                if (d[e.to] != INF)
                    continue;
                d[e.to] = d[v] + 1;
                prev_node[e.to] = v;
                q.push(e.to);
            }
        }
    }
    // 01BFS
    void zero_one_bfs(int s) {
        reset();
        deque<int> q;
        d[s] = 0;
        q.push_back(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop_front();
            for (auto &e : adj[v]) {
                ll nd = d[v] + e.cost;
                if (nd >= d[e.to])
                    continue;
                d[e.to] = nd;
                prev_node[e.to] = v;
                if (e.cost == 0)
                    q.push_front(e.to);
                else
                    q.push_back(e.to);
            }
        }
    }

    // dijkstra
    void dijkstra(int s) {
        reset();
        using P = pair<ll, int>;
        priority_queue<P, vector<P>, greater<P>> pq;
        d[s] = 0;
        pq.push({0, s});
        while (!pq.empty()) {
            auto [cost, v] = pq.top();
            pq.pop();
            if (cost > d[v])
                continue;
            for (auto &e : adj[v]) {
                ll nd = d[v] + e.cost;
                if (nd >= d[e.to])
                    continue;
                d[e.to] = nd;
                prev_node[e.to] = v;
                pq.push({nd, e.to});
            }
        }
    }

    // Bellman-Ford
    // 負閉路から到達できる頂点のdistは-INF
    // 戻り値: 負閉路が存在すれば true
    bool bellman_ford(int s) {
        reset();
        d[s] = 0;
        vector<tuple<int, int, ll>> edges;
        for (int v = 0; v < n; v++)
            for (auto &e : adj[v])
                edges.emplace_back(v, e.to, e.cost);

        for (int i = 0; i < n; i++) {
            bool updated = false;
            for (auto &[from, to, cost] : edges) {
                if (d[from] == INF)
                    continue;
                if (d[from] + cost < d[to]) {
                    d[to] = d[from] + cost;
                    prev_node[to] = from;
                    updated = true;
                    if (i == n - 1)
                        d[to] = -INF;
                }
            }
            if (!updated)
                break;
        }

        queue<int> q;
        for (int v = 0; v < n; v++)
            if (d[v] == -INF)
                q.push(v);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto &e : adj[v]) {
                if (d[e.to] != -INF) {
                    d[e.to] = -INF;
                    q.push(e.to);
                }
            }
        }

        bool has_negative_cycle = false;
        for (int v = 0; v < n; v++)
            if (d[v] == -INF) {
                has_negative_cycle = true;
                break;
            }
        return has_negative_cycle;
    }

    ll dist(int v) const {
        if (d[v] == INF)
            return -1;
        if (d[v] == -INF)
            return -2;
        return d[v];
    }

    vector<int> path(int g) const {
        if (d[g] == INF || d[g] == -INF)
            return {};
        vector<int> res;
        for (int v = g; v != -1; v = prev_node[v])
            res.push_back(v);
        reverse(res.begin(), res.end());
        return res;
    }
};

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    int h, w;
    cin >> h >> w;
    int sx, sy;
    cin >> sx >> sy;
    sx--;
    sy--;
    auto tr = [&](int i, int j, int d, int x) {
        return 2 * (9 * (i * w + j) + d) + x;
    };

    vector<string> s(h);
    rep(i, h) {
        cin >> s[i];
    }
    SSSP g(h * w * 18);
    rep(i, h) rep(j, w) {
        if (s[i][j] == '#')
            continue;
        rep(k, 8) {
            int nx = i + dx[k];
            int ny = j + dy[k];
            if (nx < 0 || ny < 0 || nx >= h || ny >= w)
                continue;
            if (s[nx][ny] == '#')
                continue;
            rep(l, 9) {
                if (k == l) {
                    g.add_edge(tr(i, j, l, 1), tr(nx, ny, k, 1), 0);
                    g.add_edge(tr(i, j, l, 0), tr(nx, ny, k, 0), 0);
                    g.add_edge(tr(i, j, l, 0), tr(nx, ny, k, 1), 1);
                    g.add_edge(tr(i, j, l, 1), tr(nx, ny, k, 0), 1);
                } else {
                    g.add_edge(tr(i, j, l, 0), tr(nx, ny, k, 1), 1);
                    g.add_edge(tr(i, j, l, 1), tr(nx, ny, k, 0), 1);
                }
            }
        }
    }
    g.zero_one_bfs(tr(sx, sy, 8, 0));
    int q;
    cin >> q;
    while (q--) {
        int d0 = 1 << 30;
        int d1 = 1 << 30;
        int gx, gy, t;
        cin >> gx >> gy >> t;
        gx--;
        gy--;
        rep(i, 9) {
            if (g.dist(tr(gx, gy, i, 0)) != -1)
                d0 = min((ll)d0, g.dist(tr(gx, gy, i, 0)));
            if (g.dist(tr(gx, gy, i, 1)) != -1)
                d1 = min((ll)d1, g.dist(tr(gx, gy, i, 1)));
        }
        if (t % 2 == 0) {
            cout << (d0 <= t ? "Yes" : "No") << endl;
        } else {
            cout << (d1 <= t ? "Yes" : "No") << endl;
        }
    }
    return 0;
}