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

• 問題: No.3806 Crossword Key with Cropping (Easy)
• ユーザー: Nihonielse
• 提出日時: 2026-10-24 12:08:48
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 60 ms / 2,000 ms
• コード長: 3,627 bytes
• コンパイル時間: 2,920 ms
• コンパイル使用メモリ: 373,920 KB
• 実行使用メモリ: 9,900 KB
• 最終ジャッジ日時: 2026-11-14 14:34:11
• 合計ジャッジ時間: 8,928 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

// 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 isWhite = [&](int i, int j) -> bool {
        return 0 <= i && i < H &&
               0 <= j && j < W &&
               S[i][j] == '.';
    };

    auto isBlack = [&](int i, int j) -> bool {
        return !isWhite(i, j);
    };

    // 境界フラグ:
    // t, b, l, r が true の方向はクエリの範囲外とみなす。
    auto keyAt = [&](int i, int j,
                     bool t, bool b, bool l, bool r) -> int {
        if (S[i][j] == '#') return 0;

        bool lb = l || isBlack(i, j - 1);
        bool rb = r || isBlack(i, j + 1);
        bool ub = t || isBlack(i - 1, j);
        bool db = b || isBlack(i + 1, j);

        bool rw = !r && isWhite(i, j + 1);
        bool dw = !b && isWhite(i + 1, j);

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

    // 盤面全体でのカギの2次元累積和
    vector<vector<int>> pref(H + 1, vector<int>(W + 1, 0));

    // 各辺のカギの1次元累積和
    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) {
            int v = keyAt(i, j, false, false, false, false);

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

            // 黒マスでも必ず累積和を更新する
            top[i][j + 1] =
                top[i][j] + keyAt(i, j, true, false, false, false);

            bottom[i][j + 1] =
                bottom[i][j] + keyAt(i, j, false, true, false, false);

            left[j][i + 1] =
                left[j][i] + keyAt(i, j, false, false, true, false);

            right[j][i + 1] =
                right[j][i] + keyAt(i, j, false, false, false, true);
        }
    }

    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なら直接数える
        if (A == C || B == D) {
            for (int i = A; i <= C; ++i) {
                for (int j = B; j <= D; ++j) {
                    ans += keyAt(
                        i, j,
                        i == A, i == C,
                        j == B, j == 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 += keyAt(A, B, true, false, true, false);
        ans += keyAt(A, D, true, false, false, true);
        ans += keyAt(C, B, false, true, true, false);
        ans += keyAt(C, D, false, true, false, true);

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

    return 0;
}