結果
問題 | No.1572 XI |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2021-06-27 15:02:45 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,830 bytes |
コンパイル時間 | 392 ms |
コンパイル使用メモリ | 82,376 KB |
実行使用メモリ | 197,108 KB |
最終ジャッジ日時 | 2024-06-25 11:47:16 |
合計ジャッジ時間 | 6,725 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 42 ms
62,616 KB |
testcase_01 | AC | 42 ms
54,548 KB |
testcase_02 | AC | 42 ms
54,500 KB |
testcase_03 | AC | 41 ms
55,544 KB |
testcase_04 | AC | 1,594 ms
116,780 KB |
testcase_05 | TLE | - |
testcase_06 | AC | 1,424 ms
153,204 KB |
testcase_07 | AC | 436 ms
82,740 KB |
testcase_08 | AC | 487 ms
142,632 KB |
testcase_09 | AC | 1,094 ms
112,012 KB |
testcase_10 | AC | 1,636 ms
132,680 KB |
testcase_11 | AC | 883 ms
90,244 KB |
testcase_12 | AC | 1,759 ms
116,600 KB |
testcase_13 | AC | 990 ms
93,792 KB |
testcase_14 | AC | 944 ms
103,824 KB |
testcase_15 | AC | 360 ms
83,884 KB |
testcase_16 | AC | 1,531 ms
111,180 KB |
testcase_17 | AC | 304 ms
80,788 KB |
testcase_18 | AC | 137 ms
103,560 KB |
testcase_19 | AC | 1,412 ms
145,356 KB |
testcase_20 | AC | 1,210 ms
121,136 KB |
testcase_21 | TLE | - |
testcase_22 | TLE | - |
testcase_23 | AC | 228 ms
80,752 KB |
testcase_24 | AC | 41 ms
55,364 KB |
testcase_25 | AC | 40 ms
56,244 KB |
testcase_26 | AC | 43 ms
57,188 KB |
testcase_27 | AC | 41 ms
54,584 KB |
testcase_28 | AC | 43 ms
56,320 KB |
testcase_29 | AC | 42 ms
55,448 KB |
testcase_30 | AC | 43 ms
56,208 KB |
testcase_31 | AC | 42 ms
54,952 KB |
testcase_32 | AC | 42 ms
56,556 KB |
testcase_33 | AC | 41 ms
55,996 KB |
testcase_34 | AC | 1,270 ms
197,108 KB |
testcase_35 | AC | 632 ms
196,508 KB |
testcase_36 | TLE | - |
testcase_37 | TLE | - |
testcase_38 | TLE | - |
testcase_39 | TLE | - |
testcase_40 | AC | 1,751 ms
193,656 KB |
testcase_41 | TLE | - |
testcase_42 | TLE | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
testcase_46 | -- | - |
testcase_47 | -- | - |
testcase_48 | -- | - |
ソースコード
""" https://yukicoder.me/problems/no/1572 サイコロの向きは、6通りしかない 頑張って推移を書けばおk 0 表 1 上 2 右 3 下 4 左 5 裏 """ import sys from sys import stdin from collections import deque def encode(x,y,state): return H*W*state + y*H + x def decode(now): state = now // (H*W) y = (now % (H*W)) // H x = (now % (H*W)) % H return x,y,state def chdi(state,movedir): if state == 0: if movedir == "U": return 1 elif movedir == "R": return 2 elif movedir == "D": return 3 else: return 4 elif state == 1: #上 if movedir == "U": return 5 elif movedir == "D": return 0 else: return 1 elif state == 2: #右 if movedir == "R": return 5 elif movedir == "L": return 0 else: return 2 elif state == 3: #下 if movedir == "D": return 5 elif movedir == "U": return 0 else: return 3 elif state == 4: #左 if movedir == "L": return 5 elif movedir == "R": return 0 else: return 4 else: #裏 if movedir == "U": return 3 elif movedir == "R": return 4 elif movedir == "D": return 1 else: return 2 H,W = map(int,stdin.readline().split()) sx,sy = map(int,stdin.readline().split()) gx,gy = map(int,stdin.readline().split()) sx -= 1 sy -= 1 gx -= 1 gy -= 1 gcode = encode(gx,gy,0) A = [ list(stdin.readline()[:-1]) for i in range(H) ] d = [float("inf")] * (H*W*6) q = deque([encode(sx,sy,0)]) d[encode(sx,sy,0)] = 0 while q: code = q.popleft() if code == gcode: break x,y,state = decode(code) if x != 0 and A[x-1][y] != "#": nx,ny,nstate = x-1,y,chdi(state,"U") ncode = encode(nx,ny,nstate) if d[ncode] > d[code] + 1: d[ncode] = d[code] + 1 q.append(ncode) if x != H-1 and A[x+1][y] != "#": nx,ny,nstate = x+1,y,chdi(state,"D") ncode = encode(nx,ny,nstate) if d[ncode] > d[code] + 1: d[ncode] = d[code] + 1 q.append(ncode) if y != 0 and A[x][y-1] != "#": nx,ny,nstate = x,y-1,chdi(state,"L") ncode = encode(nx,ny,nstate) if d[ncode] > d[code] + 1: d[ncode] = d[code] + 1 q.append(ncode) if y != W-1 and A[x][y+1] != "#": nx,ny,nstate = x,y+1,chdi(state,"R") ncode = encode(nx,ny,nstate) if d[ncode] > d[code] + 1: d[ncode] = d[code] + 1 q.append(ncode) ans = d[gcode] print (ans if ans != float("inf") else -1)