結果

問題 No.2855 Move on Grid
ユーザー Basin-BugBasin-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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 201 ms
78,348 KB
testcase_01 AC 211 ms
79,708 KB
testcase_02 AC 203 ms
78,912 KB
testcase_03 AC 141 ms
77,524 KB
testcase_04 AC 150 ms
77,644 KB
testcase_05 AC 170 ms
78,064 KB
testcase_06 AC 218 ms
79,368 KB
testcase_07 AC 97 ms
76,912 KB
testcase_08 AC 151 ms
77,880 KB
testcase_09 AC 126 ms
77,164 KB
testcase_10 AC 531 ms
98,984 KB
testcase_11 AC 407 ms
98,916 KB
testcase_12 AC 374 ms
98,808 KB
testcase_13 AC 365 ms
99,544 KB
testcase_14 AC 390 ms
99,812 KB
testcase_15 AC 379 ms
98,972 KB
testcase_16 AC 390 ms
99,828 KB
testcase_17 AC 370 ms
99,360 KB
testcase_18 AC 370 ms
99,048 KB
testcase_19 AC 411 ms
99,024 KB
testcase_20 AC 462 ms
97,064 KB
testcase_21 AC 596 ms
97,620 KB
testcase_22 AC 447 ms
97,116 KB
testcase_23 AC 470 ms
97,608 KB
testcase_24 AC 570 ms
97,820 KB
testcase_25 AC 481 ms
100,420 KB
testcase_26 AC 439 ms
97,852 KB
testcase_27 AC 463 ms
97,516 KB
testcase_28 AC 478 ms
96,924 KB
testcase_29 AC 447 ms
97,336 KB
testcase_30 AC 635 ms
99,176 KB
testcase_31 AC 464 ms
100,436 KB
testcase_32 AC 703 ms
119,732 KB
testcase_33 AC 469 ms
102,048 KB
testcase_34 AC 454 ms
100,732 KB
testcase_35 AC 496 ms
103,220 KB
testcase_36 AC 627 ms
104,820 KB
testcase_37 AC 500 ms
101,496 KB
testcase_38 AC 607 ms
102,492 KB
testcase_39 AC 645 ms
99,468 KB
権限があれば一括ダウンロードができます

ソースコード

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