結果

問題 No.2731 Two Colors
ユーザー ryohei22
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import heapq
H, 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] = 1
visit[-1][-1] = 0
n = [[(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 = 1
while 1:
if not n[idx%2]:
break
mi = 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:
break
visit[mi[1]][mi[2]] = idx % 2
fin = False
for 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 = True
break
if 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:
break
idx += 1
print(idx)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0