結果
問題 | 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 iter import collections as coll import heapq as hq import bisect as bis from decimal import Decimal as dec from copy import deepcopy as dcopy import math import sys sys.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.141592653589793 mod = 10**9+7 MOD = 998244353 INF = math.inf dx = [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]] = d if(v[0] == finish[0] and v[1] == finish[1]): break for 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] == '#'): continue for i in range(4): nx = x+dx[i]; ny = y+dy[i] if not(0 <= nx < h and 0 <= ny < w): continue if(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")