結果

問題 No.34 砂漠の行商人
ユーザー szkhtsszkhts
提出日時 2021-07-21 12:25:20
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 867 bytes
コンパイル時間 89 ms
コンパイル使用メモリ 10,916 KB
実行使用メモリ 549,920 KB
最終ジャッジ日時 2023-09-24 13:02:58
合計ジャッジ時間 11,294 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 18 ms
12,692 KB
testcase_01 AC 18 ms
8,184 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 1,391 ms
14,588 KB
testcase_08 WA -
testcase_09 MLE -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
権限があれば一括ダウンロードができます

ソースコード

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