結果
問題 | No.1638 Robot Maze |
ユーザー | MasKoaTS |
提出日時 | 2021-10-03 18:45:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 399 ms / 2,000 ms |
コード長 | 1,594 bytes |
コンパイル時間 | 302 ms |
コンパイル使用メモリ | 87,236 KB |
実行使用メモリ | 90,512 KB |
最終ジャッジ日時 | 2023-09-28 19:03:59 |
合計ジャッジ時間 | 19,348 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 236 ms
83,352 KB |
testcase_01 | AC | 233 ms
83,416 KB |
testcase_02 | AC | 231 ms
83,352 KB |
testcase_03 | AC | 348 ms
90,512 KB |
testcase_04 | AC | 233 ms
83,404 KB |
testcase_05 | AC | 231 ms
83,468 KB |
testcase_06 | AC | 232 ms
83,472 KB |
testcase_07 | AC | 231 ms
83,432 KB |
testcase_08 | AC | 234 ms
83,480 KB |
testcase_09 | AC | 231 ms
83,512 KB |
testcase_10 | AC | 231 ms
83,336 KB |
testcase_11 | AC | 234 ms
83,352 KB |
testcase_12 | AC | 239 ms
83,540 KB |
testcase_13 | AC | 233 ms
83,472 KB |
testcase_14 | AC | 297 ms
87,220 KB |
testcase_15 | AC | 338 ms
87,924 KB |
testcase_16 | AC | 344 ms
88,028 KB |
testcase_17 | AC | 361 ms
88,188 KB |
testcase_18 | AC | 251 ms
84,724 KB |
testcase_19 | AC | 344 ms
88,144 KB |
testcase_20 | AC | 345 ms
88,100 KB |
testcase_21 | AC | 293 ms
87,360 KB |
testcase_22 | AC | 291 ms
87,100 KB |
testcase_23 | AC | 297 ms
87,256 KB |
testcase_24 | AC | 290 ms
87,396 KB |
testcase_25 | AC | 289 ms
87,372 KB |
testcase_26 | AC | 316 ms
87,928 KB |
testcase_27 | AC | 324 ms
88,080 KB |
testcase_28 | AC | 337 ms
88,024 KB |
testcase_29 | AC | 332 ms
87,792 KB |
testcase_30 | AC | 230 ms
83,228 KB |
testcase_31 | AC | 229 ms
83,312 KB |
testcase_32 | AC | 347 ms
88,704 KB |
testcase_33 | AC | 358 ms
89,556 KB |
testcase_34 | AC | 324 ms
88,960 KB |
testcase_35 | AC | 377 ms
89,060 KB |
testcase_36 | AC | 338 ms
89,252 KB |
testcase_37 | AC | 362 ms
88,620 KB |
testcase_38 | AC | 258 ms
84,828 KB |
testcase_39 | AC | 358 ms
89,476 KB |
testcase_40 | AC | 356 ms
88,944 KB |
testcase_41 | AC | 368 ms
89,352 KB |
testcase_42 | AC | 320 ms
88,892 KB |
testcase_43 | AC | 399 ms
89,520 KB |
testcase_44 | AC | 359 ms
88,844 KB |
testcase_45 | AC | 332 ms
88,576 KB |
testcase_46 | AC | 344 ms
89,020 KB |
testcase_47 | AC | 347 ms
88,672 KB |
testcase_48 | AC | 340 ms
89,440 KB |
testcase_49 | AC | 383 ms
88,628 KB |
testcase_50 | AC | 364 ms
89,084 KB |
testcase_51 | AC | 346 ms
88,928 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")