結果
問題 | No.2731 Two Colors |
ユーザー |
|
提出日時 | 2024-04-19 22:05:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,558 ms / 3,000 ms |
コード長 | 1,170 bytes |
コンパイル時間 | 247 ms |
コンパイル使用メモリ | 82,408 KB |
実行使用メモリ | 119,672 KB |
最終ジャッジ日時 | 2024-10-11 15:16:26 |
合計ジャッジ時間 | 18,729 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
from heapq import heappop, heappushh, w = map(int, input().split())a = [list(map(int, input().split())) for _ in range(h)]# くっつくまでやるa_q = [(a[0][0], 0, 0)]pushed_a = [[False] * w for _ in range(h)]b_q = [(a[-1][-1], h - 1, w - 1)]pushed_b = [[False] * w for _ in range(h)]colors = [[-1] * w for _ in range(h)]go = Trueturn = 0cnt = 0DXDY = [(1, 0), (0, 1), (-1, 0), (0, -1)]while go:# print(a_q, b_q, turn)if turn == 0:_, y, x = heappop(a_q)else:_, y, x = heappop(b_q)if colors[y][x] != -1:continuecolors[y][x] = turnfor dx, dy in DXDY:nx, ny = x + dx, y + dyif 0 <= nx < w and 0 <= ny < h:if colors[ny][nx] == -1:if turn == 0 and not pushed_a[ny][nx]:heappush(a_q, (a[ny][nx], ny, nx))pushed_a[ny][nx] = Trueelif turn == 1 and not pushed_b[ny][nx]:heappush(b_q, (a[ny][nx], ny, nx))pushed_b[ny][nx] = Trueelif colors[ny][nx] != turn:go = Falseturn = 1 - turncnt += 1print(cnt - 2)