結果
問題 | 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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 157 ms
86,272 KB |
testcase_01 | AC | 146 ms
86,272 KB |
testcase_02 | AC | 142 ms
86,272 KB |
testcase_03 | AC | 263 ms
93,952 KB |
testcase_04 | AC | 144 ms
86,144 KB |
testcase_05 | AC | 148 ms
86,016 KB |
testcase_06 | AC | 144 ms
86,272 KB |
testcase_07 | AC | 151 ms
86,144 KB |
testcase_08 | AC | 158 ms
86,016 KB |
testcase_09 | AC | 159 ms
86,144 KB |
testcase_10 | AC | 160 ms
86,400 KB |
testcase_11 | AC | 159 ms
86,400 KB |
testcase_12 | AC | 161 ms
86,016 KB |
testcase_13 | AC | 145 ms
86,016 KB |
testcase_14 | AC | 216 ms
91,904 KB |
testcase_15 | AC | 251 ms
91,392 KB |
testcase_16 | AC | 248 ms
91,392 KB |
testcase_17 | AC | 265 ms
91,520 KB |
testcase_18 | AC | 166 ms
89,856 KB |
testcase_19 | AC | 262 ms
91,776 KB |
testcase_20 | AC | 284 ms
91,648 KB |
testcase_21 | AC | 221 ms
91,520 KB |
testcase_22 | AC | 226 ms
91,264 KB |
testcase_23 | AC | 232 ms
91,520 KB |
testcase_24 | AC | 217 ms
91,520 KB |
testcase_25 | AC | 213 ms
91,520 KB |
testcase_26 | AC | 227 ms
91,264 KB |
testcase_27 | AC | 238 ms
91,520 KB |
testcase_28 | AC | 247 ms
92,160 KB |
testcase_29 | AC | 244 ms
91,776 KB |
testcase_30 | AC | 144 ms
85,888 KB |
testcase_31 | AC | 143 ms
86,400 KB |
testcase_32 | AC | 265 ms
92,416 KB |
testcase_33 | AC | 267 ms
92,800 KB |
testcase_34 | AC | 236 ms
92,800 KB |
testcase_35 | AC | 284 ms
93,056 KB |
testcase_36 | AC | 248 ms
93,312 KB |
testcase_37 | AC | 271 ms
92,800 KB |
testcase_38 | AC | 170 ms
89,856 KB |
testcase_39 | AC | 259 ms
94,080 KB |
testcase_40 | AC | 261 ms
92,800 KB |
testcase_41 | AC | 253 ms
92,672 KB |
testcase_42 | AC | 232 ms
92,800 KB |
testcase_43 | AC | 334 ms
93,184 KB |
testcase_44 | AC | 281 ms
93,056 KB |
testcase_45 | AC | 265 ms
92,544 KB |
testcase_46 | AC | 267 ms
93,056 KB |
testcase_47 | AC | 258 ms
92,928 KB |
testcase_48 | AC | 250 ms
93,056 KB |
testcase_49 | AC | 292 ms
93,056 KB |
testcase_50 | AC | 260 ms
93,312 KB |
testcase_51 | AC | 257 ms
93,696 KB |
ソースコード
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")