結果

問題 No.34 砂漠の行商人
コンテスト
ユーザー szkhts
提出日時 2021-07-21 12:25:20
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 867 bytes
コンパイル時間 139 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 568,608 KB
最終ジャッジ日時 2024-07-17 13:56:20
合計ジャッジ時間 10,967 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 WA * 6 MLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import heapq

def area_chk(a, b):
    return a >= 0 and a < N and b >=0 and b < N

N, V, Sx, Sy, Gx, Gy = map(int, input().split())
Sx -= 1
Sy -= 1
Gx -= 1
Gy -= 1
sand = [list(map(int, input().split())) for _ in range(N)]

dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
dp = [[[0] * (V + 1) for _ in range(N)] for _ in range(N)]

dp[Sy][Sx][V] = 1
h = []
heapq.heappush(h, [Sy, Sx, V])

while len(h) != 0:
    y, x, v = heapq.heappop(h)

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if not area_chk(ny, nx):
            continue
        nv = v - sand[ny][nx]
        if nv <= 0:
            continue
        if dp[ny][nx][nv] != 0:
            continue
        if ny == Gy and nx == Gx:
            print(dp[y][x][v])
            sys.exit()
        dp[ny][nx][nv] = dp[y][x][v] + 1
        heapq.heappush(h, [ny, nx, nv])

print(-1)
0