結果

問題 No.2855 Move on Grid
ユーザー D M
提出日時 2025-02-11 10:45:01
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 747 ms / 3,000 ms
コード長 1,581 bytes
コンパイル時間 660 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 118,820 KB
最終ジャッジ日時 2025-02-11 10:45:29
合計ジャッジ時間 22,057 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
import sys

input = sys.stdin.readline

n, m, k = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 10


def f(x):
    # 0-1 BFS を用いて、(0,0)から(n-1,m-1)までの必要な修正回数の最小値を求める
    dist = [[INF] * m for _ in range(n)]
    dq = deque()
    # スタートセルでは、A[0][0]>=xなら修正不要（コスト0）、そうでなければ修正（コスト1）
    start_cost = 0 if A[0][0] >= x else 1
    dist[0][0] = start_cost
    dq.append((0, 0))

    while dq:
        i, j = dq.popleft()
        for di, dj in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 上下左右全ての方向
            ni, nj = i + di, j + dj
            if 0 <= ni < n and 0 <= nj < m:
                # 次のセルに入るとき、A[ni][nj]がx未満なら修正が必要
                add = 0 if A[ni][nj] >= x else 1
                if dist[ni][nj] > dist[i][j] + add:
                    dist[ni][nj] = dist[i][j] + add
                    # コストが0なら前に、1なら後ろに追加（0-1 BFSのテクニック）
                    if add == 0:
                        dq.appendleft((ni, nj))
                    else:
                        dq.append((ni, nj))
    return dist[n - 1][m - 1]


# 二分探索：答えの候補は 0〜10^9 の間
l, r = 0, 10 ** 9 + 1
while r - l > 1:
    mid = (l + r) // 2
    # midを最低値とする経路が、k回以内の修正で実現できるか判定
    if f(mid) > k:
        r = mid
    else:
        l = mid
print(l)
0