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

• 問題: No.3803 Crossword Key Checker
• ユーザー: Nihonielse
• 提出日時: 2026-10-06 14:25:36
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: WA
  (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 3,616 bytes
• コンパイル時間: 1,479 ms
• コンパイル使用メモリ: 191,816 KB
• 実行使用メモリ: 9,928 KB
• 最終ジャッジ日時: 2026-11-14 14:30:46
• 合計ジャッジ時間: 3,904 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge4_0

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

ソースコード

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

using namespace std;

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

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

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

    vector<pair<string, string>> clues;
    string r, c;
    while (cin >> r >> c) {
        clues.push_back({r, c});
    }

    // カギの開始位置を検出する
    // 各マスが横・縦のカギの開始地点であるかを判定
    struct ClueInfo {
        int r, c;
        bool is_horizontal;
        bool is_vertical;
    };

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

            bool h_start = (j == 0 || S[i][j - 1] == '#') && (j + 1 < W && S[i][j + 1] == '.');
            bool v_start = (i == 0 || S[i - 1][j] == '#') && (i + 1 < H && S[i + 1][j] == '.');

            if (h_start || v_start) {
                detected_clues.push_back({i, j, h_start, v_start});
            }
        }
    }

    if (detected_clues.size() != clues.size()) {
        cout << "No\n";
        return 0;
    }

    // 盤面上の文字を一時的に保存または検証するためのグリッド
    // 交差チェック用
    vector<vector<char>> grid_char(H, vector<char>(W, '\0'));

    for (size_t k = 0; k < detected_clues.size(); ++k) {
        int r_idx = detected_clues[k].r;
        int c_idx = detected_clues[k].c;
        string h_str = clues[k].first;
        string v_str = clues[k].second;

        // 横のカギの検証
        if (detected_clues[k].is_horizontal) {
            if (h_str == "-") {
                cout << "No\n";
                return 0;
            }
            // 白マスの長さを数える
            int len = 0;
            int cur_c = c_idx;
            while (cur_c < W && S[r_idx][cur_c] == '.') {
                len++;
                cur_c++;
            }
            if (h_str.length() != len) {
                cout << "No\n";
                return 0;
            }
            // 文字の書き込みと整合性チェック
            for (int i = 0; i < len; ++i) {
                char ch = h_str[i];
                if (grid_char[r_idx][c_idx + i] != '\0' && grid_char[r_idx][c_idx + i] != ch) {
                    cout << "No\n";
                    return 0;
                }
                grid_char[r_idx][c_idx + i] = ch;
            }
        } else {
            if (h_str != "-") {
                cout << "No\n";
                return 0;
            }
        }

        // 縦のカギの検証
        if (detected_clues[k].is_vertical) {
            if (v_str == "-") {
                cout << "No\n";
                return 0;
            }
            int len = 0;
            int cur_r = r_idx;
            while (cur_r < H && S[cur_r][c_idx] == '.') {
                len++;
                cur_r++;
            }
            if (v_str.length() != len) {
                cout << "No\n";
                return 0;
            }
            for (int i = 0; i < len; ++i) {
                char ch = v_str[i];
                if (grid_char[r_idx + i][c_idx] != '\0' && grid_char[r_idx + i][c_idx] != ch) {
                    cout << "No\n";
                    return 0;
                }
                grid_char[r_idx + i][c_idx] = ch;
            }
        } else {
            if (v_str != "-") {
                cout << "No\n";
                return 0;
            }
        }
    }

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