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()