#1191712 (Python3) No.3803 Crossword Key Checker

• 問題: No.3803 Crossword Key Checker
• ユーザー: Nihonielse
• 提出日時: 2026-10-06 15:06:07
• 言語: Python3 (3.15.2 + numpy 2.5.4 + scipy 1.18.1 + ACL)
• 結果: AC
• 実行時間: 28 ms / 2,000 ms
• コード長: 4,765 bytes
• コンパイル時間: 59 ms
• コンパイル使用メモリ: 15,360 KB
• 実行使用メモリ: 11,392 KB
• 最終ジャッジ日時: 2026-11-14 14:31:15
• 合計ジャッジ時間: 3,562 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge5_0

ファイルパターン	結果
sample	AC * 4
other	AC * 47

ソースコード

import sys


def solve():
  input = sys.stdin.read
  data = input().split()
  if not data:
    return

  H = int(data[0])
  W = int(data[1])
  S = data[2 : 2 + H]

  K = int(data[2 + H])

  R = []
  C = []
  idx = 3 + H
  for _ in range(K):
    R.append(data[idx])
    C.append(data[idx + 1])
    idx += 2

  # カギの開始位置を検出する
  # 1から始まる添字を振るため、各マスに対応する横のカギのIDと縦のカギのIDを記録する
  h_ids = [[0] * W for _ in range(H)]
  v_ids = [[0] * W for _ in range(H)]

  h_count = 0
  for r in range(H):
    for c in range(W):
        if S[r][c] == '.':
          is_start = False
          # 横のカギの開始条件：左が黒または盤面の外、かつ右が白
          left_is_black = (c == 0) or (S[r][c - 1] == '#')
          right_is_white = (c + 1 < W) and (S[r][c + 1] == '.')
          if left_is_black and right_is_white:
            is_start = True

          up_is_black = (r == 0) or (S[r - 1][c] == '#')
          down_is_white = (r + 1 < H) and (S[r + 1][c] == '.')
          if up_is_black and down_is_white:
            is_start = True

          if is_start:
            # 実際にどちらか、あるいは両方が始まるかを確認してIDを振る
            pass

  # より正確に横・縦のカギの開始位置をそれぞれ独立に番号付けする
  h_start_positions = []
  for r in range(H):
    for c in range(W):
      if S[r][c] == '.':
        left_is_black = (c == 0) or (S[r][c - 1] == '#')
        right_is_white = (c + 1 < W) and (S[r][c + 1] == '.')
        if left_is_black and right_is_white:
          h_start_positions.append((r, c))

  v_start_positions = []
  for r in range(H):
    for c in range(W):
      if S[r][c] == '.':
        up_is_black = (r == 0) or (S[r - 1][c] == '#')
        down_is_white = (r + 1 < H) and (S[r + 1][c] == '.')
        if up_is_black and down_is_white:
          v_start_positions.append((r, c))

  # 問題文によると、横のカギと縦のカギが重複する場合、どちらも同じ添字を使うとあるため、
  # 上から下、左から右へ順に番号を振る必要がある。
  # マスごとに、そこに横のカギの開始があるか、縦のカギの開始があるかを調べる。

  current_id = 1
  h_map = {}  # 座標 -> 横カギID
  v_map = {}  # 座標 -> 縦カギID

  for r in range(H):
    for c in range(W):
      if S[r][c] == '.':
        left_is_black = (c == 0) or (S[r][c - 1] == '#')
        right_is_white = (c + 1 < W) and (S[r][c + 1] == '.')
        is_h = left_is_black and right_is_white

        up_is_black = (r == 0) or (S[r - 1][c] == '#')
        down_is_white = (r + 1 < H) and (S[r + 1][c] == '.')
        is_v = up_is_black and down_is_white

        if is_h or is_v:
          if is_h:
            h_map[(r, c)] = current_id
          if is_v:
            v_map[(r, c)] = current_id
          current_id += 1

  total_keys = current_id - 1
  if total_keys != K:
    print('No')
    return

  # グリッド上の文字を管理
  grid_chars = [[None] * W for _ in range(H)]

  # 横のカギを配置
  for r in range(H):
    c = 0
    while c < W:
      if (r, c) in h_map:
        kid = h_map[(r, c)]
        word = R[kid - 1]

        # このカギが続く長さを測る
        length = 0
        cc = c
        while cc < W and S[r][cc] == '.':
          length += 1
          cc += 1

        if word != '-':
          if len(word) != length:
            print('No')
            return
          for i in range(length):
            target_r = r
            target_c = c + i
            ch = word[i]
            if (
                grid_chars[target_r][target_c] is not None
                and grid_chars[target_r][target_c] != ch
            ):
              print('No')
              return
            grid_chars[target_r][target_c] = ch
        c = cc
      else:
        c += 1

  # 縦のカギを配置
  for c in range(W):
    r = 0
    while r < H:
      if (r, c) in v_map:
        kid = v_map[(r, c)]
        word = C[kid - 1]

        length = 0
        rr = r
        while rr < H and S[rr][c] == '.':
          length += 1
          rr += 1

        if word != '-':
          if len(word) != length:
            print('No')
            return
          for i in range(length):
            target_r = r + i
            target_c = c
            ch = word[i]
            if (
                grid_chars[target_r][target_c] is not None
                and grid_chars[target_r][target_c] != ch
            ):
              print('No')
              return
            grid_chars[target_r][target_c] = ch
        r = rr
      else:
        r += 1

  print('Yes')


if __name__ == '__main__':
  solve()