結果

問題 No.2855 Move on Grid
コンテスト
ユーザー Basin-Bug
提出日時 2024-08-25 22:57:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 703 ms / 3,000 ms
コード長 849 bytes
コンパイル時間 426 ms
コンパイル使用メモリ 82,460 KB
実行使用メモリ 119,732 KB
最終ジャッジ日時 2024-08-25 22:57:31
合計ジャッジ時間 18,491 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
N, M, K = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]

steps = [(0, 1), (0, -1), (-1, 0), (1, 0)]
ok = 1
ng = 10 ** 9 + 1

def judge(m):
    G = [[10 ** 18] * M for i in range(N)]
    queue = deque([(0, 0)])
    G[0][0] = 1 if A[0][0] < m else 0

    while len(queue) != 0:
      r, c = queue.popleft()

      for x, y in steps:
        nr = r + x
        nc = c + y
        if 0 <= nr < N and 0 <= nc < M:
          if G[nr][nc] != 10 ** 18:
            continue
          if A[nr][nc] < m:
            G[nr][nc] = G[r][c] + 1
            queue.append((nr, nc))
          else:
            G[nr][nc] = G[r][c]
            queue.appendleft((nr, nc))

    return G[-1][-1] <= K

while ok + 1 < ng:
  mid = (ok + ng) // 2
  if judge(mid):
    ok = mid
  else:
    ng = mid

print(ok)
0