結果

問題 No.2855 Move on Grid
ユーザー ntuda
提出日時 2024-08-31 11:31:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 599 ms / 3,000 ms
コード長 1,080 bytes
コンパイル時間 653 ms
コンパイル使用メモリ 82,448 KB
実行使用メモリ 103,672 KB
最終ジャッジ日時 2024-08-31 11:31:23
合計ジャッジ時間 20,245 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

N, M, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
dir = [[0, 1], [1, 0], [-1, 0], [0, -1]]

def search(v):
    nv = [[True] * M for _ in range(N)]
    cnt = 0
    Q = [(0, 0)]
    if A[0][0] < v:
        cnt += 1
        if cnt > K:
            return False
    nv[0][0] = False

    while Q:
        Q2 = []
        while Q:
            x0, y0 = Q.pop()
            if x0 == N - 1 and y0 == M - 1:
                return True
            for xd, yd in dir:
                x = x0 + xd
                y = y0 + yd
                if 0 <= x < N and 0 <= y < M:
                    if nv[x][y]:
                        nv[x][y] = False
                        if A[x][y] >= v:
                            Q.append((x, y))
                        else:
                            Q2.append((x, y))
        Q, Q2 = Q2, Q
        cnt += 1
        if cnt > K:
            return False
    return cnt

lb = 1
ub = 10 ** 9 + 1
while ub - lb > 1:
    mid = (ub + lb) // 2
    if search(mid):
        lb = mid
    else:
        ub = mid
print(lb)
0