結果
問題 |
No.2855 Move on Grid
|
ユーザー |
![]() |
提出日時 | 2024-08-25 14:21:32 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 916 bytes |
コンパイル時間 | 172 ms |
コンパイル使用メモリ | 82,568 KB |
実行使用メモリ | 116,140 KB |
最終ジャッジ日時 | 2024-08-25 14:21:54 |
合計ジャッジ時間 | 17,149 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 WA * 30 |
ソースコード
from collections import* n, m, k = map(int, input().split()) a = [list(map(int, input().split())) for _ in range(n)] ng = 10 ** 9 + 1 ok = 0 while abs(ok - ng) > 1: mid = (ok + ng) // 2 # begin mid が ok かどうか判定する為の前処理 dp = [[-1] * m for _ in range(n)] dp[0][0] = int(a[0][0] > mid) q = deque([(0, 0)]) while q: i, j = q.popleft() for x, y in [(i - 1, j), (i, j - 1), (i, j + 1), (i + 1, j)]: if 0 <= x < n and 0 <= y < m and dp[x][y] == -1: if a[x][y] <= mid: dp[x][y] = dp[i][j] q.appendleft((x, y)) else: dp[x][y] = dp[i][j] + 1 q.appendleft((x, y)) # end mid が ok かどうか判定する為の前処理 if dp[-1][-1] <= k: # mid が ok の場合の条件 ok = mid else: ng = mid print(ok)