結果
問題 | No.1638 Robot Maze |
ユーザー |
![]() |
提出日時 | 2021-08-06 21:34:27 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 75 ms / 2,000 ms |
コード長 | 790 bytes |
コンパイル時間 | 301 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 11,264 KB |
最終ジャッジ日時 | 2024-09-17 01:25:23 |
合計ジャッジ時間 | 4,065 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
import sys input = sys.stdin.readline import heapq H,W=map(int,input().split()) U,D,R,L,K,P=map(int,input().split()) xs,ys,xt,yt=map(int,input().split()) MAP=[input().strip() for i in range(H)] DP=[[1<<60]*W for i in range(H)] xs-=1 xt-=1 ys-=1 yt-=1 Q=[(0,xs,ys)] while Q: cost,x,y=heapq.heappop(Q) if cost>DP[x][y]: continue for z,w,cp in [(x+1,y,D),(x-1,y,U),(x,y+1,R),(x,y-1,L)]: if 0<=z<H and 0<=w<W: if MAP[z][w]=="." and DP[z][w]>cost+cp: DP[z][w]=cost+cp heapq.heappush(Q,(cost+cp,z,w)) elif MAP[z][w]=="@" and DP[z][w]>cost+cp+P: DP[z][w]=cost+cp+P heapq.heappush(Q,(cost+cp+P,z,w)) if DP[xt][yt]<=K: print("Yes") else: print("No")