結果
問題 | No.179 塗り分け |
ユーザー |
![]() |
提出日時 | 2023-02-21 14:25:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 286 ms / 3,000 ms |
コード長 | 1,685 bytes |
コンパイル時間 | 383 ms |
コンパイル使用メモリ | 82,392 KB |
実行使用メモリ | 77,176 KB |
最終ジャッジ日時 | 2024-07-22 01:49:36 |
合計ジャッジ時間 | 6,035 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 40 |
ソースコード
# まず黒マスは偶数個である必要 # どの黒マスとどの黒マスをペアにするか、そのペア間の(i, j)距離 # その距離で全部の黒マスをペアリングできるか H, W = map(int, input().split()) S = [] for i in range(H): S.append(input()) blacks = [] count = 0 count_matrix = [[-1]*W for h in range(H)] for i in range(H): for j in range(W): if S[i][j] == '#': blacks.append((count, (i, j))) count_matrix[i][j] = count count += 1 black_total = count ans = 'NO' didj_visited = set() if black_total%2 == 0: for a in range(black_total): for b in range(a+1, black_total): di = blacks[b][1][0]-blacks[a][1][0] dj = blacks[b][1][1]-blacks[a][1][1] if (di, dj) in didj_visited: continue didj_visited.add((di, dj)) test = True visited = set() for c in range(black_total): if blacks[c][0] in visited: continue visited.add(blacks[c][0]) if not (0 <= blacks[c][1][0]+di < H and 0 <= blacks[c][1][1]+dj < W): test = False break nxt_num = count_matrix[blacks[c][1][0]+di][blacks[c][1][1]+dj] if nxt_num in visited or nxt_num == -1: test = False break else: visited.add(nxt_num) if test == True and len(visited) == black_total: ans = 'YES' #print(blacks[a], blacks[b], di, dj) print(ans)