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

• 問題: No.3806 Crossword Key with Cropping (Easy)
• ユーザー: Nihonielse
• 提出日時: 2026-10-24 12:18:38
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 3,715 bytes
• コンパイル時間: 1,435 ms
• コンパイル使用メモリ: 185,908 KB
• 実行使用メモリ: 9,928 KB
• 最終ジャッジ日時: 2026-11-14 14:34:58
• 合計ジャッジ時間: 41,094 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	WA * 2
other	AC * 3 WA * 42 TLE * 6 -- * 2

ソースコード

// Gemini 3

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int H, W;
    if (!(cin >> H >> W)) return 0;

    vector<string> S(H);
    for (int i = 0; i < H; ++i) {
        cin >> S[i];
    }

    // 1マスカギであるかをあらかじめ判定しておく (2次元配列)
    // 1マスカギ: 白マスかつ上下左右が黒マスまたは盤面の外
    vector<vector<int>> is_one(H, vector<int>(W, 0));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (S[i][j] != '.') continue;
            bool u = (i == 0 || S[i - 1][j] == '#');
            bool d = (i == H - 1 || S[i + 1][j] == '#');
            bool l = (j == 0 || S[i][j - 1] == '#');
            bool r = (j == W - 1 || S[i][j + 1] == '#');
            if (u && d && l && r) {
                is_one[i][j] = 1;
            }
        }
    }

    // 2次元累積和 (1マスカギ用)
    vector<vector<int>> sum_one(H + 1, vector<int>(W + 1, 0));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            sum_one[i + 1][j + 1] = sum_one[i][j + 1] + sum_one[i + 1][j] - sum_one[i][j] + is_one[i][j];
        }
    }

    auto get_one = [&](int A, int B, int C, int D) {
        return sum_one[C + 1][D + 1] - sum_one[A][D + 1] - sum_one[C + 1][B] + sum_one[A][B];
    };

    int Q;
    if (!(cin >> Q)) return 0;

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

        long long ans = 0;

        // 1. 1マスカギの集計
        ans += get_one(A, B, C, D);

        // 2. 横のカギの集計 (領域内の各行について判定)
        // 横のカギ条件: 白マスかつ (左が領域外or#) かつ (右が白マスかつ領域内)
        for (int i = A; i <= C; ++i) {
            for (int j = B; j <= D; ++j) {
                if (S[i][j] != '.') continue;
                if (is_one[i][j]) continue; // 1マスカギは除外

                bool left_ok = (j == B || S[i][j - 1] == '#');
                bool right_ok = (j < D && S[i][j + 1] == '.');
                if (left_ok && right_ok) {
                    ans++;
                }
            }
        }

        // 3. 縦のカギの集計 (領域内の各列について判定)
        // 縦のカギ条件: 白マスかつ (上が領域外or#) かつ (下が白マスかつ領域内)
        for (int j = B; j <= D; ++j) {
            for (int i = A; i <= C; ++i) {
                if (S[i][j] != '.') continue;
                if (is_one[i][j]) continue; // 1マスカギは除外

                bool up_ok = (i == A || S[i - 1][j] == '#');
                bool down_ok = (i < C && S[i + 1][j] == '.');
                if (up_ok && down_ok) {
                    ans++;
                }
            }
        }

        // 4. 横のカギかつ縦のカギを両方満たすもの（重複分の調整）
        for (int i = A; i <= C; ++i) {
            for (int j = B; j <= D; ++j) {
                if (S[i][j] != '.') continue;
                if (is_one[i][j]) continue;

                bool left_ok = (j == B || S[i][j - 1] == '#');
                bool right_ok = (j < D && S[i][j + 1] == '.');
                bool up_ok = (i == A || S[i - 1][j] == '#');
                bool down_ok = (i < C && S[i + 1][j] == '.');

                if (left_ok && right_ok && up_ok && down_ok) {
                    ans--; // 横と縦の両方でカウントされてしまっているため1つ引く
                }
            }
        }

        cout << ans << "\n";
    }

    return 0;
}