結果
問題 | No.1638 Robot Maze |
ユーザー |
![]() |
提出日時 | 2021-10-03 18:45:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 334 ms / 2,000 ms |
コード長 | 1,594 bytes |
コンパイル時間 | 190 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 94,080 KB |
最終ジャッジ日時 | 2024-07-21 13:46:07 |
合計ジャッジ時間 | 13,588 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
import itertools as iterimport collections as collimport heapq as hqimport bisect as bisfrom decimal import Decimal as decfrom copy import deepcopy as dcopyimport mathimport syssys.setrecursionlimit(10**6)def input():return sys.stdin.readline().rstrip()def getN():return int(sys.stdin.readline().rstrip())def getNs():return map(int,sys.stdin.readline().rstrip().split())def getList():return list(map(int,sys.stdin.readline().rstrip().split()))def strinps(n):return [sys.stdin.readline().rstrip() for _ in range(n)]pi = 3.141592653589793mod = 10**9+7MOD = 998244353INF = math.infdx = [1,0,-1,0]; dy = [0,1,0,-1]#Dijkstra's algorithm(2 dimension)def dijkstra(route,start,finish,h,w):path = [[-1]*w for _ in range(h)]q = [(0,start)]while(q):d,v = hq.heappop(q)if(path[v[0]][v[1]] == -1):path[v[0]][v[1]] = dif(v[0] == finish[0] and v[1] == finish[1]):breakfor nv,dist in route[v[0]][v[1]]:hq.heappush(q,(d+dist,nv))return path[finish[0]][finish[1]]"""Main Code"""h,w = getNs()U,D,R,L,K,P = getNs()sx,sy,gx,gy = [i-1 for i in getNs()]s = strinps(h)route = [[[] for _ in [0]*w] for _ in [0]*h]dir = [D,R,U,L]for x in range(h):for y in range(w):if(s[x][y] == '#'):continuefor i in range(4):nx = x+dx[i]; ny = y+dy[i]if not(0 <= nx < h and 0 <= ny < w):continueif(s[nx][ny] == '.'):route[x][y].append(((nx,ny),dir[i]))elif(s[nx][ny] == '@'):route[x][y].append(((nx,ny),dir[i]+P))d = dijkstra(route,(sx,sy),(gx,gy),h,w)if(d == -1 or d > K):print("No")else:print("Yes")