結果

問題 No.2855 Move on Grid
コンテスト
ユーザー navel_tos
提出日時 2025-02-04 21:49:39
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,516 bytes
コンパイル時間 567 ms
コンパイル使用メモリ 82,684 KB
実行使用メモリ 109,528 KB
最終ジャッジ日時 2025-02-04 21:50:44
合計ジャッジ時間 42,932 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder2855 Move on Grid

#入力受取
N, M, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

#N, Mでは管理しにくいのでH, Wに。さらにAを一次元化
H, W = N, M
B = [A[i][j] for i in range(H) for j in range(W)]

#Bの各要素とindexをソート
D = {10 ** 9: []}
for i, Bi in enumerate(B):
    try: D[Bi].append(i)
    except: D[Bi] = [i]
key = sorted( D.keys(), reverse = True )

#初期状態の最短路を計算: (0, 0)と(-1, -1)の進入コストも1となる
C = [(h + w + 1) for h in range(H) for w in range(W)]

#更新。BFSの更新回数が sum(C) <= O(H * W * 2HW) で抑えられる点に注意
dial = [[] for _ in range(H + W)]
for Bi in key:
    #1. D[Bi]の到達コストを1下げる
    while D[Bi]:
        assert C[ i := D[Bi].pop() ] >= 1
        C[i] -= 1
        dial[ C[i] ].append(i)

    #2. 最短路を更新  Dial algoを回せばOK
    for c in range( C[-1] + 1 ):
        while dial[c]:
            i = dial[c].pop()
            if C[i] < c:
                continue
            assert C[i] == c
            if i % W < W - 1:
                if C[ j := i + 1 ] > ( x := C[i] + (B[j] < Bi) ):
                    C[j] = x
                    dial[x].append(j)
            if i < (H - 1) * W:
                if C[ j := i + W ] > ( x := C[i] + (B[j] < Bi) ):
                    C[j] = x
                    dial[x].append(j)

    #3. C[-1] <= Kとなれば答えを出力
    if C[-1] <= K:
        print(Bi)
        break
0