結果

問題 No.1572 XI
ユーザー persimmon-persimmonpersimmon-persimmon
提出日時 2021-07-02 10:23:37
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,385 bytes
コンパイル時間 617 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 183,176 KB
最終ジャッジ日時 2024-12-19 17:38:13
合計ジャッジ時間 40,052 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 44 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""
4 4
1 1
4 4
....
..##
#...
#...
->6
"""
h,w=map(int,input().split())
s=list(map(int,input().split()))
g=list(map(int,input().split()))
a=[input() for _ in range(h)]
s[0],s[1]=s[0]-1,s[1]-1
g[0],g[1]=g[0]-1,g[1]-1
seen=[-1]*(h*w*6)
# seen[(i*h+j)*6+x]:マス(i,j)でさいころの状態がx
# x=0:1が上,
# x=1:1が右側(wの+方向),
# x=2:1が左側(wの-方向),
# x=3:1が奥側(hの+方向),
# x=4:1が手前側(hの-方向),
# x=5:1が下
trans=lambda i,j,x:(i*w+j)*6+x
seen[trans(s[0],s[1],0)]=0
d={}
# 1上の状態から
d[(0,1,0)]=1
d[(0,-1,0)]=2
d[(1,0,0)]=3
d[(-1,0,0)]=4
# 1右の状態から
d[(0,1,1)]=5
d[(0,-1,1)]=0
d[(1,0,1)]=1
d[(-1,0,1)]=1
# 1左の状態から
d[(0,1,2)]=0
d[(0,-1,2)]=5
d[(1,0,2)]=2
d[(-1,0,2)]=2
# 1奥の状態から
d[(0,1,3)]=3
d[(0,-1,3)]=3
d[(1,0,3)]=5
d[(-1,0,3)]=0
# 1手前の状態から
d[(0,1,4)]=4
d[(0,-1,4)]=4
d[(1,0,4)]=0
d[(-1,0,4)]=5
# 1下の状態から
d[(0,1,5)]=2
d[(0,-1,5)]=1
d[(1,0,5)]=4
d[(-1,0,5)]=3


from collections import deque
todo=deque([[s[0],s[1],0]])
while todo:
  i,j,x=todo.popleft()
  for di,dj in ((0,1),(0,-1),(1,0),(-1,0)):
    ni,nj=i+di,j+dj
    if not 0<=ni<h:continue
    if not 0<=nj<w:continue
    if a[ni][nj]=="#":continue
    nx=d[(di,dj,x)]
    if seen[trans(ni,nj,nx)]==-1:
      seen[trans(ni,nj,nx)]=seen[trans(i,j,x)]+1
      todo.append([ni,nj,nx])
print(seen[trans(g[0],g[1],0)])
0