結果
問題 | No.2855 Move on Grid |
ユーザー |
![]() |
提出日時 | 2024-08-25 14:30:00 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 638 ms / 3,000 ms |
コード長 | 911 bytes |
コンパイル時間 | 374 ms |
コンパイル使用メモリ | 82,460 KB |
実行使用メモリ | 115,036 KB |
最終ジャッジ日時 | 2024-08-25 14:30:20 |
合計ジャッジ時間 | 17,695 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
from collections import*n, m, k = map(int, input().split())a = [list(map(int, input().split())) for _ in range(n)]ng = 10 ** 9 + 1ok = 0while 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] + 1q.append((x, y))else:dp[x][y] = dp[i][j]q.appendleft((x, y))# end mid が ok かどうか判定する為の前処理if dp[-1][-1] <= k: # mid が ok の場合の条件ok = midelse:ng = midprint(ok)