#1191705 (C++23(gcc16)) No.3803 Crossword Key Checker

• 問題: No.3803 Crossword Key Checker
• ユーザー: Nihonielse
• 提出日時: 2026-10-06 14:28:12
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: WA
  (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 4,394 bytes
• コンパイル時間: 3,205 ms
• コンパイル使用メモリ: 376,372 KB
• 実行使用メモリ: 9,928 KB
• 最終ジャッジ日時: 2026-11-14 14:30:50
• 合計ジャッジ時間: 5,579 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

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

ソースコード

#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;

    // 盤面からカギの開始位置を復元する。
    // (r, c) ごとに、横・縦のどちらか一方でもカギがあれば
    // 1つの添字を持つ。
    struct KeyPos {
        int r, c;
        bool horizontal;
        bool vertical;
    };

    vector<KeyPos> keys;

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

            bool horizontal =
                (c == 0 || S[r][c - 1] == '#') &&
                (c + 1 < W && S[r][c + 1] == '.');

            bool vertical =
                (r == 0 || S[r - 1][c] == '#') &&
                (r + 1 < H && S[r + 1][c] == '.');

            if (horizontal || vertical) {
                keys.push_back({r, c, horizontal, vertical});
            }
        }
    }

    // 入力される R_i, C_i を読む。
    vector<pair<string, string>> clues;
    string R, C;
    while (cin >> R >> C) {
        clues.emplace_back(R, C);
    }

    // カギの個数が一致する必要がある。
    if (clues.size() != keys.size()) {
        cout << "No\n";
        return 0;
    }

    // 各白マスが実際にカギで使われているかを管理する。
    vector<vector<bool>> usedH(H, vector<bool>(W, false));
    vector<vector<bool>> usedV(H, vector<bool>(W, false));

    // 交差部分の文字を記録する。
    vector<vector<char>> board(H, vector<char>(W, '?'));

    for (int k = 0; k < (int)keys.size(); ++k) {
        auto [r, c, hasH, hasV] = keys[k];
        auto [rs, cs] = clues[k];

        // -------------------------
        // 横のカギ
        // -------------------------
        if (hasH) {
            if (rs == "-") {
                cout << "No\n";
                return 0;
            }

            int len = 0;
            while (c + len < W && S[r][c + len] == '.') {
                ++len;
            }

            // 横の白マスの長さと答えの長さが一致する必要がある。
            if ((int)rs.size() != len) {
                cout << "No\n";
                return 0;
            }

            for (int x = 0; x < len; ++x) {
                int nc = c + x;
                usedH[r][nc] = true;

                if (board[r][nc] != '?' &&
                    board[r][nc] != rs[x]) {
                    cout << "No\n";
                    return 0;
                }

                board[r][nc] = rs[x];
            }
        } else {
            // 横カギが存在しないなら "-" でなければならない。
            if (rs != "-") {
                cout << "No\n";
                return 0;
            }
        }

        // -------------------------
        // 縦のカギ
        // -------------------------
        if (hasV) {
            if (cs == "-") {
                cout << "No\n";
                return 0;
            }

            int len = 0;
            while (r + len < H && S[r + len][c] == '.') {
                ++len;
            }

            // 縦の白マスの長さと答えの長さが一致する必要がある。
            if ((int)cs.size() != len) {
                cout << "No\n";
                return 0;
            }

            for (int x = 0; x < len; ++x) {
                int nr = r + x;
                usedV[nr][c] = true;

                if (board[nr][c] != '?' &&
                    board[nr][c] != cs[x]) {
                    cout << "No\n";
                    return 0;
                }

                board[nr][c] = cs[x];
            }
        } else {
            // 縦カギが存在しないなら "-" でなければならない。
            if (cs != "-") {
                cout << "No\n";
                return 0;
            }
        }
    }

    // すべての白マスが横・縦のカギによって
    // ちょうど使われていることを確認する。
    for (int r = 0; r < H; ++r) {
        for (int c = 0; c < W; ++c) {
            if (S[r][c] == '.') {
                if (!usedH[r][c] && !usedV[r][c]) {
                    cout << "No\n";
                    return 0;
                }
            }
        }
    }

    cout << "Yes\n";
    return 0;
}