結果
問題 | No.2855 Move on Grid |
ユーザー |
👑 |
提出日時 | 2024-08-25 15:04:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 907 ms / 3,000 ms |
コード長 | 1,181 bytes |
コンパイル時間 | 144 ms |
コンパイル使用メモリ | 82,544 KB |
実行使用メモリ | 120,228 KB |
最終ジャッジ日時 | 2024-08-25 15:05:23 |
合計ジャッジ時間 | 26,011 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
from collections import dequen, m, K = map(int, input().split())A = [list(map(int, input().split())) for _ in range(n)]l = 0r = 10**9 + 1di = [0, 1, 0, -1]dj = [1, 0, -1, 0]def ok(x):dist = [[1 << 30] * m for _ in range(n)]dist[0][0] = 0if A[0][0] < x:dist[0][0] = 1used = [[False] * m for _ in range(n)]queue = deque()queue.append(0)while queue:tmp = queue.popleft()i = tmp // mj = tmp - i * mif used[i][j]:continueused[i][j] = Trued = dist[i][j]for k in range(4):ni = i + di[k]nj = j + dj[k]if ni < 0 or ni >= n or nj < 0 or nj >= m:continueif A[ni][nj] >= x:if dist[ni][nj] > d:dist[ni][nj] = dqueue.appendleft(ni * m + nj)else:if dist[ni][nj] > d + 1:dist[ni][nj] = d + 1queue.append(ni * m + nj)return dist[n - 1][m - 1] <= Kwhile r - l > 1:mid = (l + r) // 2if ok(mid):l = midelse:r = midprint(l)