結果
問題 | No.2731 Two Colors |
ユーザー |
|
提出日時 | 2024-05-03 21:43:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,245 ms / 3,000 ms |
コード長 | 1,067 bytes |
コンパイル時間 | 260 ms |
コンパイル使用メモリ | 81,964 KB |
実行使用メモリ | 265,136 KB |
最終ジャッジ日時 | 2024-11-25 02:26:42 |
合計ジャッジ時間 | 23,536 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
import heapqH, W = map(int, input().split())A = [list(map(int, input().split())) for _ in range(H)]if H == W == 2:print(0)exit()visit = [[-1] * W for _ in range(H)]visit[0][0] = 1visit[-1][-1] = 0n = [[(A[H-1][W-2], H-1, W-2), (A[H-2][W-1], H-2, W-1)], [(A[0][1], 0, 1), (A[1][0], 1, 0)]]s = [set([(H-1, W-2), (H-2, W-1)]), set([(0, 1), (1, 0)])]heapq.heapify(n[0])heapq.heapify(n[1])idx = 1while 1:if not n[idx%2]:breakmi = heapq.heappop(n[idx%2])while visit[mi[1]][mi[2]] != -1 and n[idx%2]:mi = heapq.heappop(n[idx%2])if visit[mi[1]][mi[2]] != -1:breakvisit[mi[1]][mi[2]] = idx % 2fin = Falsefor i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:if 0 <= mi[1] + i < H and 0 <= mi[2] + j < W and visit[mi[1]+i][mi[2]+j] == (idx+1) % 2:fin = Truebreakif 0 <= mi[1] + i < H and 0 <= mi[2] + j < W and visit[mi[1]+i][mi[2]+j] == -1 and (mi[1]+i, mi[2]+j) not in s[idx%2]:heapq.heappush(n[idx%2], (A[mi[1]+i][mi[2]+j], mi[1]+i, mi[2]+j))s[idx%2].add((mi[1]+i, mi[2]+j))if fin:breakidx += 1print(idx)