Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Runtime Error

Solution code:
from collections import deque  

def check(zh):
    if 0<=zh[0]<H and 0<=zh[1]<W:
        return True
    else:
        return False

H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
Ch,Cw,Dh,Dw=Ch-1,Cw-1,Dh-1,Dw-1

board=[list(input()) for _ in range(H)]
INF=10**9
costs=[[INF]*W for _ in range(H)]
costs[Ch][Cw]=0

d = deque()
d.append((Ch,Cw))


while True:
    d_warp = deque()

    while d:
        st=d.pop()
        st_h,st_w=st[0],st[1]
        cost_st=costs[st_h][st_w]
        
        # warp
        for dh in [-2,-1,0,1,2]:
            for dw in [-2,-1,0,1,2]:
                if not ((abs(dh)==1 and dw==0) or (dh==0 and abs(dw)==1)):
                    tozh=(st_h+dh,st_w+dw)
                    if check(tozh) and board[tozh[0]][tozh[1]]=='.' and costs[tozh[0]][tozh[1]]>cost_st:
                        costs[tozh[0]][tozh[1]]=cost_st+1
                        d_warp.append(tozh)
        
        # walk
        for tozh in [(st_h+1,st_w),(st_h-1,st_w),(st_h,st_w+1),(st_h,st_w-1)]:
            if check(tozh) and board[tozh[0]][tozh[1]]=='.' and costs[tozh[0]][tozh[1]]>cost_st:
                costs[tozh[0]][tozh[1]]=cost_st
                d.append(tozh)
    d=d_warp
    print(d)
    aa
print(costs)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
nx,ny=map(int,input().split())
gx,gy=map(int,input().split())
maze=inputs()
#0 based index (0始まり)にする
nx-=1;ny-=1;gx-=1;gy-=1
from collections import deque
#dqが徒歩、2が魔法での移動を入れる
dq=deque([(nx,ny)])
dq2=deque([])
#かかるコストを保存しておく
T=[[float('inf')]*w for  a in range(h)]
#初期値は0で、スタート地点に保存
T[nx][ny]=0
#徒歩でのx,yの差分
moves=((1,0),(-1,0),(0,1),(0,-1))
from itertools import product as pr
#魔法での移動の差分、tuple( (i,j) |-2<=i,j<=2かつ(i,j)!=(0,0)  )と等価
Mmoves=tuple(i for i in pr((-2,-1,0,1,2),repeat=2)if i!=(0,0) )

while dq:
    #先に徒歩で行けるだけ行きたいので、徒歩を使い切るまでは魔法で行った地点たちに手を出さない
    while dq:
        x,y=dq.popleft()
        for i,j in moves:
            nex,ney=x+i,y+j
            #盤面の外や壁にぶつかるのは除外
            if not(0<=nex<h and 0<=ney<w) or maze[nex][ney]==35:continue
            if T[x][y]<T[nex][ney]:
                #コストを更新できるなら改めて捜査
                T[nex][ney]=T[x][y]
                dq.append((nex,ney))
        for i,j in Mmoves:
            nex,ney=x+i,y+j
            if not(0<=nex<h and 0<=ney<w) or maze[nex][ney]==35:continue
            if T[x][y]+1<T[nex][ney]:
                T[nex][ney]=T[x][y]+1
                dq2.append((nex,ney))
    #徒歩で行ける地点を使い切ったので、今度は魔法で行ける地点を捜査
    dq,dq2=dq2,dq
if T[gx][gy]==float('inf'):print(-1)
else:print(T[gx][gy])

Submission status: Runtime Error

Solution code:
from collections import deque
h, w = map(int, input().split())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
move1 = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
    py, px = d.popleft()
    #move1 bfs
    for dy, dx in move1:
        if 0 <= py + dy < w and 0 <= px + dx < h:
            childy = py + dy
            childx = px + dx
            if s[childy][childx] == "." and meiro[childy][childx] > meiro[py][px]:
                meiro[childy][childx] = meiro[py][px]
                d.appendleft([childy, childx])
                # move1のbfsを優先的に探索したいからd.appendleftする

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            if 0<=warpx<w and 0<=warpy<h:
                warpx = px + dx
                warpy = py + dy
                if s[warpy][warpx] == "." and meiro[warpy][warpx] > meiro[py][px]:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])


ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0

while q:
    kyori, fro_h, fro_w=q.popleft()
    if d[(fro_h, fro_w)]<kyori: continue
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori, to_h, to_w))

    try:
        #ワープ
        for dh,dw in WARP:
            to_h, to_w=fro_h+dh, fro_w+dw
            if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
                if kyori+1 < d[(to_h, to_w)]:
                    d[(to_h, to_w)]=kyori+1
                    q.append((kyori+1, to_h, to_w))
    except:
        pass

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0

while q:
    kyori, fro_h, fro_w=q.popleft()
    if d[(fro_h, fro_w)]<kyori: continue
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori, to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori+1 < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori+1
                q.append((kyori+1, to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

ch-=1
cw-=1
dh-=1
dw-=1

S=[]
for _ in range(h):
  s=input()
  sl=[]
  for i in range(w):
    sl.append(s[i])
  S.append(sl)

def isable(X):
  xh,xw=X[0],X[1]
  if 0<=xh<=h-1 and 0<=xw<=w-1 and S[xh][xw]=='.':
    return True
  else:
    return False

def stepA(X):
  xh,xw=X[0],X[1]
  A=[]
  for p,q in [(-1,0),(0,1),(1,0),(0,-1)]:
    if isable([xh+p,xw+q]):
      A.append([xh+p,xw+q])
  return A
    
def stepB(X):
  xh,xw=X[0],X[1]
  B=[]
  for i in range(-2,3):
    for j in range(-2,3):
      if i==0 and j==0:
        continue
      if isable([xh+i,xw+j]):
        B.append([xh+i,xw+j])
  return B

Q=deque()
Q.appendleft((ch,cw))
cost=[[float('inf') for i in range(w)] for j in range(h)]
cost[ch][cw]=0

while Q:
  ph,pw=Q.popleft()
  for v in stepA([ph,pw]):
    ah,aw=v[0],v[1]
    if isable([ah,aw]):
      if cost[ah][aw]>cost[ph][pw]:
        cost[ah][aw]=cost[ph][pw]
        Q.appendleft([ah,aw])
  for bh,bw in stepB([ph,pw]):
    if isable([bh,bw]):
      if cost[bh][bw]>cost[ph][pw]+1:
        cost[bh][bw]=cost[ph][pw]+1
        Q.append([bh,bw])

if cost[dh][dw]==float('inf'):
  print(-1)
else:
  print(cost[dh][dw])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0
visit[(CH,CW)]=1

while q:
    kyori, fro_h, fro_w=q.popleft()
    visit[(fro_h, fro_w)]=1
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
            if kyori < d[(to_h, to_w)]:
                visit[(to_h, to_w)]=1
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori,to_h, to_w))

    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
            if kyori+1 < d[(to_h, to_w)]:
                visit[(to_h, to_w)]=1
                d[(to_h, to_w)]=kyori+1
                q.append((kyori+1,to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0
visit[(CH,CW)]=1

while q:
    kyori, fro_h, fro_w=q.popleft()
    visit[(fro_h, fro_w)]=1
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
            if kyori < d[(to_h, to_w)]:
                visit[(to_h, to_w)]=1
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori,to_h, to_w))

    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
            if kyori+1 < d[(to_h, to_w)]:
                #visit[(to_h, to_w)]=1
                d[(to_h, to_w)]=kyori+1
                q.append((kyori+1,to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc176/submissions/16164430?lang=ja
import heapq

h, w = map(int, input().split())
sh, sw = map(lambda x: int(x) - 1, input().split())
gh, gw = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(h)]

inf = 10 ** 10
D = [[inf] * w for i in range(h)]

D[sh][sw] = 0
Q = [(0, (sh, sw))]
heapq.heapify(Q)
while Q:
  curr_h, curr_w = heapq.heappop(Q)
  for di in range(-2, 3):
    for dj in range(-2, 3):
      next_h, next_w = curr_h + di, curr_w + dj
      if 0 <= next_h < h and 0 <= next_w < w and S[next_h][next_w] == ".":
        nex = int(abs(di) + abs(dj) != 1)
        if D[next_h][next_w] > D[curr_h][curr_w] + nex:
          D[next_h][next_w] = D[curr_h][curr_w] + nex
          heapq.heappush(Q, (next_h, next_w))
if D[gh][gw] >= inf:
  print(-1)
else:
  print(D[gh][gw])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit1=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
visit2=defaultdict(lambda: 0) #未訪問:0 訪問済み:1

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit1[(to_h, to_w)]==0:
            if d[(fro_h, fro_w)] < d[(to_h, to_w)]:
                visit1[(to_h, to_w)]=1
                d[(to_h, to_w)]=d[(fro_h, fro_w)]
                q.appendleft((to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit2[(to_h, to_w)]==0:
            if d[(fro_h, fro_w)]+1 < d[(to_h, to_w)]:
                visit2[(to_h, to_w)]=1
                d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
                q.append((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit1=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
visit2=defaultdict(lambda: 0) #未訪問:0 訪問済み:1

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit1[(to_h, to_w)]==0:
            visit1[(to_h, to_w)]=1
            d[(to_h, to_w)]=d[(fro_h, fro_w)]
            q.appendleft((to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit2[(to_h, to_w)]==0:
            if d[(fro_h, fro_w)]+1 < d[(to_h, to_w)]:
                visit2[(to_h, to_w)]=1
                d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
                q.append((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    visit[(fro_h, fro_w)]=1
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
            visit[(to_h, to_w)]=1
            d[(to_h, to_w)]=d[(fro_h, fro_w)]
            q.appendleft((to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
            if d[(fro_h, fro_w)]+1 < d[(to_h, to_w)]:
                d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
                q.append((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    visit[(fro_h, fro_w)]=1
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
            visit[(to_h, to_w)]=1
            d[(to_h, to_w)]=d[(fro_h, fro_w)]
            q.appendleft((to_h, to_w))

print d[(DH,DW)]

Submission status: Runtime Error

Solution code:
import queue
 
H,W=map(int,input().split())
C=[int(i)-1 for i in input().split()]
D=[int(i)-1 for i in input().split()]
 
c=[]
for i in [0]*H:
    c.append(input())
    
    
dicA=[(-1,0),(1,0),(0,1),(0,-1),(0,0)]
dicB=[]
for i in range(-2,3):
    for j in range(-2,3):
        if i!=0 or j!=0:
            dicB.append((i,j))
    
vis=[[-1]*W for _ in [0]*H]
 
q=queue.Queue()
q.put((C[1],C[0]))
res=-1
mag=0
pre=[]
 
while 1:
    while not q.empty():
        x,y=q.get()
        if (x,y) in pre:
                pre.remove((x,y))
        for dx,dy in dicA:
            nx,ny=x+dx,y+dy
            if (nx,ny)==(D[1],D[0]):
                res=vis[ny][nx]
            if 0<=nx<=W-1 and 0<=ny<=H-1:
                if vis[ny][nx]<0 and c[ny][nx]!='#':
                    q.put((nx,ny))
                    vis[ny][nx]=mag
        for dx,dy in dicB:
            nx,ny=x+dx,y+dy
            if 0<=nx<=W-1 and 0<=ny<=H-1:
                if vis[ny][nx]<0 and c[ny][nx]=='.':
                    if not (nx,ny) in pre:
                        pre.append((nx,ny))
    if res>-1:
        break
    if pre:
        mag+=1
        for i in pre:
            q.put(i)
        pre=[]
    else:
        break
 
                
print(res)
import queue

H,W=map(int,input().split())
C=[int(i)-1 for i in input().split()]
D=[int(i)-1 for i in input().split()]

c=[]
for i in [0]*H:
    c.append(input())
    
    
dicA=[(-1,0),(1,0),(0,1),(0,-1),(0,0)]
dicB=[]
for i in range(-2,3):
    for j in range(-2,3):
        if i!=0 or j!=0:
            dicB.append((i,j))
    
vis=[[-1]*W for _ in [0]*H]

q=queue.Queue()
q.put((C[1],C[0]))
res=-1
mag=0
pre=[]

while 1:
    while not q.empty():
        x,y=q.get()
        if (x,y) in pre:
                pre.remove((x,y))
        for dx,dy in dicA:
            nx,ny=x+dx,y+dy
            if (nx,ny)==(D[1],D[0]):
                res=vis[ny][nx]
            if 0<=nx<=W-1 and 0<=ny<=H-1:
                if vis[ny][nx]<0 and c[ny][nx]!='#':
                    q.put((nx,ny))
                    vis[ny][nx]=mag
        for dx,dy in dicB:
            nx,ny=x+dx,y+dy
            if 0<=nx<=W-1 and 0<=ny<=H-1:
                if vis[ny][nx]<0 and c[ny][nx]=='.':
                    if not (nx,ny) in pre:
                        pre.append((nx,ny))
    if res>-1:
        break
    if pre:
        mag+=1
        for i in pre:
            q.put(i)
        pre=[]
    else:
        break

                
print(res)
提出情報

Submission status: Runtime Error

Solution code:
from collections import deque
HW = input().split()
H, W = int(HW[0]), int(HW[1])
C = input().split()
Ch, Cw = int(C[0]), int(C[1])
D = input().split()
Dh, Dw = int(D[0]), int(D[1])
route = []
for h in range(H):
    route.append(input())


visited = [[False]*W for x in range(H)]
kouho = deque()
kouho.append([Ch-1, Cw-1])
warpkouho = deque()

def check_walk(a, b):
    if 0 <= a <= H-1 and 0 <= b <= W-1: 
        if visited[a][b] == False and route[a][b] == ".":
            kouho.append([a, b])
def check_warp(a, b, cwarp):
    if 0 <= a <= H-1 and 0 <= b <= W-1:
        if visited[a][b] == False and route[a][b] == ".":
            warpkouho.append([a, b, cwarp+1])

def wizard():
    warp = 1
    while True:
        if len(kouho) != 0:
            tmp = kouho.popleft()
        elif len(warpkouho) != 0:
            tmp = warpkouho.popleft()
            warp = tmp[2]
        else:
            break
        h = tmp[0]
        w = tmp[1]
        if visited[h][w] == False:
            visited[h][w] = warp
            check_walk(h-1, w)
            check_walk(h+1, w)
            check_walk(h, w-1)
            check_walk(h, w+1)
            for n in range(5):
                for m in range(5):
                  	if not((n==2 and m==(1 or 2 or 3))or(n==1 and m == 2)or(n == 3 and m ==2)):                    	
                    check_warp(h-2+n, w-2+m, warp)
    if h == Dh-1 and w == Dw-1:
      	print(visited[h][w]-1)
      	return
    print(-1)
wizard()

Submission status: Runtime Error

Solution code:
import numpy as np
inf = 10 ** 9
from collections import deque
def bfs(sx, sy):
    cost = [[inf] * w for i in range(h)]
    d = ((0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (-1, 1), (1, -1), (-1, -1))
    cost[sx - 1][sy - 1] = 0
    q = deque()
    q.append((sx - 1, sy - 1))
    
    while q:
        s, t = q.popleft()
        for dx, dy in d:
            nx = s + dx
            ny = t + dy
            
            if not(0 <= nx < h and 0 <= ny < w):continue
            if cost[nx][ny] <= cost[s][t]:continue
            if (dx + dy)%2 == 0:
                if c[nx][ny] == '.' and cost[nx][ny] > cost[s][t] + 1:
                    cost[nx][ny] = cost[s][t] + 1
                    if (nx, ny) == (dh - 1, dw - 1):
                        q.append((nx, ny))

                next_d = ((dx, 0), (0, dy), (dx, dy))
                for ddx, ddy in next_d:
                    nnx = nx + ddx
                    nny = ny + ddy
                    if not(0 <= nnx < h and 0 <= nny < w):continue
                    if c[nnx][nny] == '#':continue
                    if cost[nnx][nny] <= cost[s][t] + 1:continue
                    cost[nnx][nny] = cost[s][t] + 1
                    
                    if (nnx, nny) == (dh - 1, dw - 1):continue
                    q.append((nnx, nny))
                continue
                    
            elif c[nx][ny] == '.' and (dx + dy)%2 != 0:
                cost[nx][ny] = min(cost[nx][ny], cost[s][t])
                
            elif c[nx][ny] == '#' and (dx + dy)%2 != 0:
                nx += dx
                ny += dy
                if not(0 <= nx < h and 0 <= ny < w):continue
                if c[nx][ny] == '#':continue
                if cost[nx][ny] <= cost[s][t] + 1:continue
                cost[nx][ny] = cost[s][t] + 1
                
            if (nx, ny) == (dh - 1, dw - 1):continue
            q.append((nx, ny))

    return cost
        
h, w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
c = [list(input()) for _ in range(h)]

res = bfs(ch, cw)
if res[dh - 1][dw - 1] == inf:print(-1)
else:print(res[dh - 1][dw - 1])

Submission status: Runtime Error

Solution code:
import numpy as np
inf = 10 ** 9
from collections import deque
def bfs(sx, sy):
    cost = [[inf] * w for i in range(h)]
    d = ((0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (-1, 1), (1, -1), (-1, -1))
    cost[sx - 1][sy - 1] = 0
    q = deque()
    q.append((sx - 1, sy - 1))
    
    while q:
        s, t = q.popleft()
        for dx, dy in d:
            nx = s + dx
            ny = t + dy
            
            if not(0 <= nx < h and 0 <= ny < w):continue
            if cost[nx][ny] <= cost[s][t]:continue
            if (dx + dy)%2 == 0:
                if c[nx][ny] == '.' and cost[nx][ny] > cost[s][t] + 1:
                    cost[nx][ny] = cost[s][t] + 1
                    if (nx, ny) == (dh - 1, dw - -1):
                        q.append((nx, ny))

                next_d = ((dx, 0), (0, dy), (dx, dy))
                for ddx, ddy in next_d:
                    nnx = nx + ddx
                    nny = ny + ddy
                    if not(0 <= nnx < h and 0 <= nny < w):continue
                    if c[nnx][nny] == '#':continue
                    if cost[nnx][nny] <= cost[s][t] + 1:continue
                    cost[nnx][nny] = cost[s][t] + 1
                    
                    if (nnx, nny) == (dh - 1, dw - 1):continue
                    q.append((nnx, nny))
                continue
                    
            elif c[nx][ny] == '.' and (dx + dy)%2 != 0:
                cost[nx][ny] = min(cost[nx][ny], cost[s][t])
                
            elif c[nx][ny] == '#' and (dx + dy)%2 != 0:
                nx += dx
                ny += dy
                if not(0 <= nx < h and 0 <= ny < w):continue
                if c[nx][ny] == '#':continue
                if cost[nx][ny] <= cost[s][t] + 1:continue
                cost[nx][ny] = cost[s][t] + 1
                
            if (nx, ny) == (dh - 1, dw - 1):continue
            q.append((nx, ny))

    return cost
        
h, w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
c = [list(input()) for _ in range(h)]

res = bfs(ch, cw)
if res[dh - 1][dw - 1] == inf:print(-1)
else:print(res[dh - 1][dw - 1])

Submission status: Runtime Error

Solution code:
import sys
import math
import heapq

(h, w) = [int(x) for x in sys.stdin.readline().strip().split(" ")]
(c_h, c_w) = [int(x) for x in sys.stdin.readline().strip().split(" ")]
(d_h, d_w) = [int(x) for x in sys.stdin.readline().strip().split(" ")]

maze = []
for line in sys.stdin:
    maze.append(list(line.strip())) 

def isReachable(i, j):
    if i < 1 or i > h or j < 1 or j > w:
        return False

    c = maze[i-1][j - 1]
    if c == '#':
        return False
    else:
        return True

def distance(fp, tp):
    if not isReachable(tp[1], tp[2]):
        return None

    h_diff = math.fabs(tp[1] - fp[1])
    w_diff = math.fabs(tp[2] - fp[2])

    if h_diff + w_diff < 2:
        return 0

    if h_diff < 3 or w_diff < 3:
        return 1

def adjacents(current):
    adjs = []
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == 0 and j == 0:
                continue
            dst = (None, current[1] + i, current[2] + j)
            dist = distance(current, dst)
            if dist is not None:
                dst = (dist, dst[1], dst[2])
                adjs.append(dst)

    return adjs

@njit
def dijkstra(results, start):
    """Calcualte the distance from start points to all the node
    """
    cur_dist = 0
    results[start[1] - 1][start[2] -1] = cur_dist
    heap = [ (p[0] + cur_dist, p[1], p[2]) for p in  adjacents(start) ]
    heapq.heapify(heap)

    while len(heap) > 0:
        visited = heapq.heappop(heap)
        if results[visited[1] - 1][visited[2] -1] is not None:
            continue

        results[visited[1] - 1][visited[2] -1] = visited[0]
        cur_dist = visited[0]

        adjs = list(filter(lambda x: results[x[1] - 1][x[2] - 1] is None, adjacents(visited)))

        for a in [(p[0] + cur_dist, p[1], p[2]) for p in adjs]:
            heapq.heappush(heap, a)


results = [[None] * w for i in range(0, h)]
start = (0, c_h, c_w)

dijkstra(results, start)

if results[d_h - 1][d_w -1] is None:
    print(-1)
else:
    print(results[d_h - 1][d_w -1])

Submission status: Runtime Error

Solution code:
import sys
import math
import heapq

(h, w) = [int(x) for x in sys.stdin.readline().strip().split(" ")]
(c_h, c_w) = [int(x) for x in sys.stdin.readline().strip().split(" ")]
(d_h, d_w) = [int(x) for x in sys.stdin.readline().strip().split(" ")]

maze = []
for line in sys.stdin:
    maze.append(list(line.strip())) 

def isReachable(i, j):
    if i < 1 or i > h or j < 1 or j > w:
        return False

    c = maze[i-1][j - 1]
    if c == '#':
        return False
    else:
        return True

def distance(fp, tp):
    if not isReachable(tp[1], tp[2]):
        return None

    h_diff = math.fabs(tp[1] - fp[1])
    w_diff = math.fabs(tp[2] - fp[2])

    if h_diff + w_diff < 2:
        return 0

    if h_diff < 3 or w_diff < 3:
        return 1

def adjacents(current):
    adjs = []
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == 0 and j == 0:
                continue
            dst = (None, current[1] + i, current[2] + j)
            dist = distance(current, dst)
            if dist is not None:
                dst = (dist, dst[1], dst[2])
                adjs.append(dst)

    return adjs

def dijkstra(results, start):
    """Calcualte the distance from start points to all the node
    """
    cur_dist = 0
    results[start[1] - 1][start[2] -1] = cur_dist
    heap = [ (p[0] + cur_dist, p[1], p[2]) for p in  adjacents(start) ]
    heapq.heapify(heap)

    while len(heap) > 0:
        visited = heapq.heappop(heap)
        if results[visited[1] - 1][visited[2] -1] is not None:
            continue

        results[visited[1] - 1][visited[2] -1] = visited[0]
        cur_dist = visited[0]

        adjs = list(filter(lambda x: results[x[1] - 1][x[2] - 1] is None, adjacents(visited)))

        for a in [(p[0] + cur_dist, p[1], p[2]) for p in adjs]:
            heapq.heappush(heap, a)


@njit((b1[:, :], i8, i8, i8, i8), cache=True)
def main():
    results = [[None] * w for i in range(0, h)]
    start = (0, c_h, c_w)

    dijkstra(results, start)

    if results[d_h - 1][d_w -1] is None:
        print(-1)
    else:
        print(results[d_h - 1][d_w -1])

main()