#1194888 (C++23(gcc16)) No.3806 Crossword Key with Cropping (Easy)

• 問題: No.3806 Crossword Key with Cropping (Easy)
• ユーザー: Nihonielse
• 提出日時: 2026-10-24 12:06:52
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 4,098 bytes
• コンパイル時間: 2,758 ms
• コンパイル使用メモリ: 373,992 KB
• 実行使用メモリ: 9,932 KB
• 最終ジャッジ日時: 2026-11-14 14:33:52
• 合計ジャッジ時間: 7,749 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge1_0

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

ソースコード

// GPT-6 Instant

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W;
    cin >> H >> W;

    vector<string> S(H);
    for (auto &s : S) cin >> s;

    // 盤面外は黒マスとして扱う
    auto black = [&](int i, int j) -> bool {
        if (i < 0 || i >= H || j < 0 || j >= W)
            return true;
        return S[i][j] == '#';
    };

    auto white = [&](int i, int j) -> bool {
        return 0 <= i && i < H &&
               0 <= j && j < W &&
               S[i][j] == '.';
    };

    // 内部のマスがカギかどうか
    vector<vector<int>> pref(H + 1, vector<int>(W + 1, 0));

    // 各辺にあるマスがカギかどうか
    vector<vector<int>> top(H, vector<int>(W + 1, 0));
    vector<vector<int>> bottom(H, vector<int>(W + 1, 0));
    vector<vector<int>> left(W, vector<int>(H + 1, 0));
    vector<vector<int>> right(W, vector<int>(H + 1, 0));

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (S[i][j] == '#') continue;

            bool lb = black(i, j - 1);
            bool rb = black(i, j + 1);
            bool ub = black(i - 1, j);
            bool db = black(i + 1, j);

            bool rw = white(i, j + 1);
            bool dw = white(i + 1, j);

            // 内部のマス
            int key =
                (lb && rw) ||
                (ub && dw) ||
                (lb && rb && ub && db);

            pref[i + 1][j + 1] =
                pref[i][j + 1] + pref[i + 1][j]
                - pref[i][j] + key;

            // 上辺：上が範囲外
            top[i][j + 1] = top[i][j] +
                (lb && rw || dw || lb && rb && db);

            // 下辺：下が範囲外
            bottom[i][j + 1] = bottom[i][j] +
                (lb && rw || lb && rb && ub);

            // 左辺：左が範囲外
            left[j][i + 1] = left[j][i] +
                (rw || ub && dw || ub && db && rb);

            // 右辺：右が範囲外
            right[j][i + 1] = right[j][i] +
                (ub && dw || ub && db && lb);
        }
    }

    // クエリの範囲内の1マスについて、カギか判定する
    auto isKey = [&](int i, int j,
                     int A, int B, int C, int D) -> int {
        if (S[i][j] == '#') return 0;

        bool lb = (j == B || black(i, j - 1));
        bool rb = (j == D || black(i, j + 1));
        bool ub = (i == A || black(i - 1, j));
        bool db = (i == C || black(i + 1, j));

        bool rw = (j < D && white(i, j + 1));
        bool dw = (i < C && white(i + 1, j));

        return (lb && rw) ||
               (ub && dw) ||
               (lb && rb && ub && db);
    };

    // 2次元累積和で [A..C] x [B..D] を取得
    auto rectSum = [&](int A, int B, int C, int D) -> int {
        if (A > C || B > D) return 0;
        return pref[C + 1][D + 1]
             - pref[A][D + 1]
             - pref[C + 1][B]
             + pref[A][B];
    };

    int Q;
    cin >> Q;

    while (Q--) {
        int A, B, C, D;
        cin >> A >> B >> C >> D;
        --A; --B; --C; --D;

        int ans = 0;

        // 高さ1または幅1なら直接調べる
        if (A == C || B == D) {
            for (int i = A; i <= C; i++) {
                for (int j = B; j <= D; j++) {
                    ans += isKey(i, j, A, B, C, D);
                }
            }
            cout << ans << '\n';
            continue;
        }

        // 内部
        ans += rectSum(A + 1, B + 1, C - 1, D - 1);

        // 上辺・下辺（角を除く）
        ans += top[A][D] - top[A][B + 1];
        ans += bottom[C][D] - bottom[C][B + 1];

        // 左辺・右辺（角を除く）
        ans += left[B][C] - left[B][A + 1];
        ans += right[D][C] - right[D][A + 1];

        // 四隅はクエリの境界条件で直接判定
        ans += isKey(A, B, A, B, C, D);
        ans += isKey(A, D, A, B, C, D);
        ans += isKey(C, B, A, B, C, D);
        ans += isKey(C, D, A, B, C, D);

        cout << ans << '\n';
    }

    return 0;
}