結果
問題 | No.2731 Two Colors |
ユーザー |
|
提出日時 | 2024-04-14 12:49:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,654 ms / 3,000 ms |
コード長 | 785 bytes |
コンパイル時間 | 324 ms |
コンパイル使用メモリ | 82,384 KB |
実行使用メモリ | 129,028 KB |
最終ジャッジ日時 | 2024-10-03 13:32:16 |
合計ジャッジ時間 | 18,876 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
from heapq import *H, W = map(int, input().split())A = [list(map(int, input().split())) for _ in range(H)]q = [[], []]C = [[[-1] * W for _ in range(H)] for _ in range(2)]B = [[[0] * W for _ in range(H)] for _ in range(2)]heappush(q[1], (A[0][0], 0, 0))heappush(q[0], (A[H - 1][W - 1], H - 1, W - 1))B[1][0][0] = 1B[0][H - 1][W - 1] = 1for k in range(1, H * W + 1):_, i, j = heappop(q[k % 2])C[k % 2][i][j] = 0for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:x = i + dxy = j + dyif 0 <= x < H and 0 <= y < W:if C[1 - k % 2][x][y] == 0:exit(print(k - 2))for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:x = i + dxy = j + dyif 0 <= x < H and 0 <= y < W:if B[k % 2][x][y] == 0:heappush(q[k % 2], (A[x][y], x, y))B[k % 2][x][y] = 1