結果
問題 | No.34 砂漠の行商人 |
ユーザー |
|
提出日時 | 2023-03-19 08:02:06 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 212 ms / 5,000 ms |
コード長 | 818 bytes |
コンパイル時間 | 214 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 11,264 KB |
最終ジャッジ日時 | 2024-09-18 13:41:29 |
合計ジャッジ時間 | 3,168 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
import collections import sys 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 i in range(N)] dxy = [(1,0),(-1,0),(0,-1),(0,1)] dxy = [(1,0),(-1,0),(0,-1),(0,1)] lstimes = [[0]*(N) for i in range(N)] lscost = [[float('INF')]*N for i in range(N)] lscost[Sy][Sx] = 0 d = collections.deque([(Sy,Sx)]) while d: x,y = d.popleft() if x == Gy and y == Gx: if lscost[x][y] < V: print(lstimes[x][y]) sys.exit() for dx,dy in dxy: if 0<= x+dx < N and 0 <= y+dy < N: if lscost[x+dx][y+dy] > lscost[x][y] + sand[x+dx][y+dy]: lscost[x+dx][y+dy] = lscost[x][y] + sand[x+dx][y+dy] lstimes[x+dx][y+dy] = lstimes[x][y]+1 d.append((x+dx,y+dy)) print(-1)