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
#import sys
#sys.setrecursionlimit(6000)

def dfs(start_h, start_w, S, H, W):
    path = deque()
    path.append((start_h, start_w))
    visited = set()
    #DFS
    while path:
        p = path.pop()
        if p in visited:
            continue
        visited.add(p)
        x, y = p
        for xx, yy in [(x,y+1), (x, y-1), (x+1, y), (x-1, y)]:
            if xx<0 or yy<0 or xx>H or yy>W:
                #print("Not exist:", xx, yy)
                continue
            #print(f"xx, yy={xx},{yy}")
            if S[yy][xx]:
                path.append((xx, yy))
    return visited

def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [[False]*(W+1)]  #S[w][h]でアクセス すなわちy,x
    for _ in range(W):
        S.append([False] + [True if x=='.' else False for x in input()])
    #DFS
    total_visited = set()
    visited = dfs(Ch, Cw, S, H, W)
    total_visited = total_visited.union(visited)
    if (Dh, Dw) in total_visited:
        print(0)
        exit()

    ans = 0
    while True:
        new_dist = set()
        for p in total_visited:
            x, y = p
            for xx, yy in [(x,y+2), (x, y-2), (x+2, y), (x-2, y)]:
                if xx<0 or yy<0 or xx>H or yy>W:
                    #print("Not exist:", xx, yy)
                    continue
                if (xx, yy) in total_visited:
                    continue
                if S[yy][xx]:
                    new_dist.add((xx, yy))
        #print(total_visited)
        #print(new_dist)
        kono = set()
        for dist in new_dist:
            x, y = dist
            if dist in total_visited:
                continue
            #print(f'new dist={x},{y}')
            new_visited = dfs(x, y, S, H, W)
            #print(f'new_visited={new_visited}')
            if new_visited:
                total_visited = total_visited.union(new_visited)
                ans += 1
                kono = kono.union(new_visited)
        if not kono:
            break
    if (Dh, Dw) in total_visited:
        print(ans)
    else:
        print(-1)




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
maze = [[9]*(w+2)]
for i in range(h):
  s = input()
  tmp = [9]
  for i in s:
    if i == "#":
      tmp.append(9)
    else:
      tmp.append(0)
  tmp.append(9)
  maze.append(tmp)
maze.append([9]*(w+2))
#print(maze)

pos = deque()
pos.append([ch,cw,0])
while len(pos)>0:
  x, y, hop = pos.popleft(()
  #print(x,y,hop)
  if (x,y) == (dh,dw):
    print(hop)
    break
    
  maze[x][y] = 2
  
  flag = 0
  if maze[x-1][y] <2:
    pos.append([x-1,y,hop])
    flag = 1
  if maze[x+1][y] <2:
    pos.append([x+1,y,hop])
    flag = 1
  if maze[x][y-1] <2:
    pos.append([x,y-1,hop])
    flag = 1
  if maze[x][y+1] <2:
    pos.append([x,y+1,hop])
    flag = 1
    
  if flag == 0:
    try:
      if maze[x-2][y] <2:
        pos.append([x-2,y,hop+1])
    except:
      pass
    
    try:
      if maze[x-2][y+1] <2:
        pos.append([x-2,y+1,hop+1])
    except:
      pass
        
    try: 
      if maze[x-2][y+2] <2:
        pos.append([x-2,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x-2][y-1] <2:
        pos.append([x-2,y-1,hop+1])
    except:
      pass
    
    try:
      if maze[x-2][y-2] <2:
        pos.append([x-2,y-2,hop+1])
    except:
      pass
    
    try:
      if maze[x+2][y] <2:
        pos.append([x+2,y,hop+1])
    except:
      pass
    try:
      if maze[x+2][y-1] <2:
        pos.append([x+2,y-1,hop+1])
    except:
      pass
    try:
      if maze[x+2][y-2] <2:
        pos.append([x+2,y-2,hop+1])
    except:
      pass
    try:
      if maze[x+2][y+1] <2:
        pos.append([x+2,y+1,hop+1])
    except:
      pass
    
    try:
      if maze[x+2][y+2] <2:
        pos.append([x+2,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x][y-2] <2:
        pos.append([x,y-2,hop+1])
    except:
      pass
    
    try:
      if maze[x+1][y-2] <2:
        pos.append([x+1,y-2,hop+1])
    except:
      pass
    try:
      if maze[x-1][y-2] <2:
        pos.append([x-1,y-2,hop+1])
    except:
      pass
    
    try:
      if maze[x][y+2] <2:
        pos.append([x,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x+1][y+2] <2:
        pos.append([x+1,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x-1][y+2] <2:
        pos.append([x-1,y+2,hop+1])
    except:
      pass
    if maze[x-1][y-1] <2:
      pos.append([x-1,y-1,hop+1])
    if maze[x-1][y+1] <2:
      flag=1
      pos.append([x-1,y+1,hop+1])
    if maze[x+1][y-1] <2:
      flag=1
      pos.append([x+1,y-1,hop+1])
    if maze[x+1][y+1] <2:
      flag=1
      pos.append([x+1,y+1,hop+1])
    
else:
  print(-1)

Submission status: Runtime Error

Solution code:
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

#input = sys.stdin.readline

########################################
def valid(a,b):
	#print(a,b)
	if 0<=a<=h-1 and 0<=b<=w-1 and arr[a][b] == ".":
		return True
	else:
		return False


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
arr = [list(input()) for i in range(h)]
#print(arr)
can_vis = []
dist = [[float("inf")]*w for i in range(h)]
q = deque()
ans = float("inf")
q.append((ch,cw,0))
dist[ch][cw] = 0
#print(dh,dw,ch,cw)
while q:
	#print(q.popleft())
	#print(q)
	curx , cury = q.popleft()
	#can_vis.append((curx,cury))
	f = 0
	if curx == dh and cury == dw:
		ans = min(ans, magic)
	for dx,dy in [[1,0],[0,1],[-1,0],[0,-1]]:
		if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
			dist[curx+dx][cury+dy] = dist[curx][cury]
			q.append((curx+dx, cury+dy))
	for dx in range(-2,3):
		for dy in range(-2,3):
			if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
				dist[curx+dx][cury+dy] = dist[curx][cury] + 1 
				q.append((curx+dx, cury+dy))


if dist[dh][dw] == float("inf"):
	print(-1)
else:
	print(dist[dh][dw])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()


def main():
    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
    s2 = [list(input()) for i in range(h)]
    s2[Ch][Cw] = 0
    d = deque()
    d.append([Ch, Cw])
    while d:
        nowh, noww = d.popleft()
        for i, j in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                if s2[nowh+i][noww+j] == '.':
                    s2[nowh+i][noww+j] = s2[nowh][noww]
                    d.appendleft([nowh+i, nowh+j])
                elif s2[nowh+i][noww+j] != '#':
                    if s2[nowh+i][noww+j] > s2[nowh][noww]:
                        s2[nowh+i][noww+j] = s2[nowh][noww]
                        d.append([nowh+i, noww+j])
        for i,j in [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,1],[-1,2],[0,-2],[0,2],[1,-2],[1,-1],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]:
            if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                if s2[nowh+i][noww+j] == '.':
                    s2[nowh+i][noww+j] = s2[nowh][noww]+1
                    d.append([nowh+i, noww+j])
                elif s2[nowh+i][noww+j] != '#':
                    if s2[nowh+i][noww+j] > s2[nowh][noww]+1:
                        s2[nowh+i][noww+j] = s2[nowh][noww]+1
                        d.append([nowh+i, noww+j])

    if s2[Dh][Dw] == '.':
        print(-1)
    else:
        print(s2[Dh][Dw])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from copy import deepcopy as dp
from pprint import pprint as print


h, w = map(int, input().split())
c = tuple(map(int, input().split()))
d = tuple(map(int, input().split()))
s = []
for i in range(h):
    tmp = []
    for x in input():
        if x == '#':
            tmp.append(0)
        else:
            tmp.append(1)
    s.append(tmp)


def dfs(m, i, j, k):
    if m[i][j] != 1:
        return
    else:
        m[i][j] = k

        if i - 1 >= 0 and m[i - 1][j] == 1:
            dfs(m, i - 1, j, k)

        if j - 1 >= 0 and m[i][j - 1] == 1:
            dfs(m, i, j - 1, k)

        if j + 1 < w and m[i][j + 1] == 1:
            dfs(m, i, j + 1, k)

        if i + 1 < h and m[i + 1][j] == 1:
            dfs(m, i + 1, j, k)


u = 1
for a in range(h):
    for b in range(w):
        u += 1
        dfs(s, a, b, u)

dic_base = {}
for a in range(h):
    for b in range(w):
        tmp = s[a][b]
        if tmp == 0:
            continue
        if tmp not in dic_base.keys():
            dic_base[tmp] = set()
        h_s = max(0, a - 2)
        h_e = min(h - 1, a + 2)
        w_s = max(0, b - 2)
        w_e = min(w - 1, b + 2)

        for a_i in range(h_s, h_e + 1):
            for b_j in range(w_s, w_e + 1):
                if s[a_i][b_j] not in [0, tmp]:
                    dic_base[tmp].add(s[a_i][b_j])

g_s = s[c[0] - 1][c[1] - 1]
g_e = s[d[0] - 1][d[1] - 1]
ans = float('inf')


def dfs2(next_cod, path):
    global ans
    if next_cod == g_e:
        if ans > len(path) - 1:
            ans = len(path) - 1
        return
    if len(dic_base[next_cod]) == 0:
        return
    else:
        for cod in dic_base[next_cod]:
            if cod not in path:
                next_path = dp(path) + [cod]
                dfs2(cod, next_path)


dfs2(g_s, [g_s])
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

dx=[0,1,0,-1]
dy=[1,0,-1,0]

def bfs(ans):
  ans[ch-1][cw-1]=0
  qu = deque([])
  qu.append([cw-1,ch-1])
  for i in range(cw-1-2,cw-1+3):
    for j in range(ch-1-2,ch-1+3):
      if 0<=i<w and 0<=j<h:
        if maze[j][i]=="." and (ans[j][i]>ans[ch][cw]+1 or ans[j][i]==-1):
          ans[j][i]=(ans[ch][cw]+1)
          qu.append([i,j])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    if x==dw-1 and y==dh-1:
      break
    count=0
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h and maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):

        qu.append([x+dx[i],y+dy[i]])
        ans[y+dy[i]][x+dx[i]] = ans[y][x]
        if i==0:
          for j in range(-2,3):
            if 0 <= x+dx[i]+j < w and 0 <= y+dy[i]+2 < h and maze[y+dy[i]][x+dx[i]+j]=="." and (ans[y+dy[i]+2][x+dx[i]+j]>ans[y][x]+1 or ans[y+dy[i]+2][x+dx[i]+j]==-1):
              qu.append([x+dx[i]+j,y+dy[i]+2])
              ans[y+dy[i]+2][x+dx[i]+j] = ans[y][x]+1
        elif i==2:
          for j in range(-2,3):
            if 0 <= x+dx[i]+j < w and 0 <= y+dy[i]-2 < h and maze[y+dy[i]][x+dx[i]+j]=="." and (ans[y+dy[i]-2][x+dx[i]+j]>ans[y][x]+1 or ans[y+dy[i]-2][x+dx[i]+j]==-1):
              qu.append([x+dx[i]+j,y+dy[i]-2])
              ans[y+dy[i]-2][x+dx[i]+j] = ans[y][x]+1
              
        elif i==1:
          for j in range(-2,3):
            if 0 <= x+dx[i]+2 < w and 0 <= y+dy[i]+j < h and maze[y+dy[i]+j][x+dx[i]+2]=="." and (ans[y+dy[i]+j][x+dx[i]+2]>ans[y][x]+1 or ans[y+dy[i]+j][x+dx[i]+2]==-1):
              qu.append([x+dx[i]+2,y+dy[i]+j])
              ans[y+dy[i]+j][x+dx[i]+2] = ans[y][x]+1
        else:
          for j in range(-2,3):
            if 0 <= x+dx[i]-2 < w and 0 <= y+dy[i]+j < h and maze[y+dy[i]+j][x+dx[i]-2]=="." and (ans[y+dy[i]-j][x+dx[i]-2]>ans[y][x]+1 or ans[y+dy[i]-j][x+dx[i]-2]==-1):
              qu.append([x+dx[i]-2,y+dy[i]+j])
              ans[y+dy[i]+j][x+dx[i]-2] = ans[y][x]+1


bfs(ans)
print(ans[dh-1][dw-1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
n,m = map(int,input().split())
si,sj = map(int,input().split())
si,sj = si-1,sj-1
ei,ej = map(int,input().split())
ei,ej = ei-1,ej-1

mat = []
for _ in range(n):
    l = input()
    mat.append(l)
    
def getChildren(i,j):
    c = []
    for il in [-2,-1,0,1,2]:
        for jl in [-2,-1,0,1,2]:
            if il==0 and jl==0:continue
            ssi,ssj = i+il,j+jl
            isnear = int(not(((il==1 and jl==0) or (il==0 and jl==1) or (il==-1 and jl==0) or (il==0 and jl==-1))))
            if 0<=i+il<=n-1 and 0<=j+jl<=m-1 and mat[ssi][ssj]==".":
                c.append([ssi,ssj,isnear])
    return c
memo = {}
def dfs(i,j):
    #print("Reached:",i,j)
    if i==ei and j==ej:
        return 0
    if (i,j) in memo:
        return memo[(i,j)]
    children = getChildren(i,j)
    memo[(i,j)] = float("inf")
    for child in children:
        memo[(i,j)] = min(memo[(i,j)],dfs(child[0],child[1]) + child[2])
    return memo[(i,j)]
ans = dfs(si,sj)
if ans == float("inf"):
    ans = -1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
n,m = map(int,input().split())
si,sj = map(int,input().split())
si,sj = si-1,sj-1
ei,ej = map(int,input().split())
ei,ej = ei-1,ej-1

mat = []
for _ in range(n):
    l = input()
    mat.append(l)
    
def getChildren(i,j):
    c = []
    for il in [-2,-1,0,1,2]:
        for jl in [-2,-1,0,1,2]:
            if il==0 and jl==0:continue
            ssi,ssj = i+il,j+jl
            isnear = int(not(((il==1 and jl==0) or (il==0 and jl==1) or (il==-1 and jl==0) or (il==0 and jl==-1))))
            if 0<=i+il<=n-1 and 0<=j+jl<=m-1 and mat[ssi][ssj]==".":
                c.append([ssi,ssj,isnear])
    return c
memo = {}
def dfs(i,j):
    #print("Reached:",i,j)
    if i==ei and j==ej:
        return 0
    if (i,j) in memo:
        return memo[(i,j)]
    children = getChildren(i,j)
    memo[(i,j)] = float("inf")
    for child in children:
        memo[(i,j)] = min(memo[(i,j)],dfs(child[0],child[1]) + child[2])
    return memo[(i,j)]
ans = dfs(si,sj)
if ans == float("inf"):
    ans = -1
print(ans)

Submission status: Runtime Error

Solution code:
def myfunc(h, w, c):
    if 0<=h and h<H+2 and 0<=w and w<W+2 and T[h][w] != '#':
        if T[h][w] == '.' or T[h][w] > c:
            T[h][w] = c
            global warp
            for i in [(0,1), (0,-1), (1,0), (-1,0)]:
                myfunc(h+i[0], w+i[1], c)
                for k in range(-2, 3):
                    for l in range(-2, 3):
                        myfunc(h+k, w+l, T[h][w]+1)

H, W= map(int, input().split())
CH, CW= map(int, input().split())
DH, DW= map(int, input().split())
S = ['#'+input()+'#' for _ in range(H)]
S.insert(0,'#'*(W*2))
S.append('#'*(W*2))
T = [[0] * (W+2) for _ in range(H+2)]
for i in range(H+2):
    for j in range(W+2):
        T[i][j] = S[i][j]
myfunc(CH, CW, 0)
warp = True
# while T[DH][DW] == '.' and warp:
#     warp = False
#     for i in range(H+2):
#         for j in range(W+2):
#             if T[i][j] != '.' and T[i][j] != '#':
#                 for k in range(-2, 3):
#                     for l in range(-2, 3):
#                         myfunc(i+k, j+l, T[i][j]+1)
if T[DH][DW] == '#' or T[DH][DW] == '.':
    print(-1)
else:
    print(T[DH][DW])

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())

L = []
for i in range(h):
    L.append(input())
visited = [[0]*w for i in range(h)]   

from collections import deque
li1 = [(1,0),(0,1),(-1,0),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]
li2 = [(2,0),(0,2),(-2,0),(0,-2),(2,2),(2,-2),(-2,2),(-2,-2)]

d = deque([[sy,sx]])
#print(d.popleft())
cnt =0

while d:
    [a,b] = d.popleft()
    flag = True
    for (dy,dx) in li1:
        if 0 <=a+dy<h and 0<=b+dx<w and visited[a+dy][b +dx] ==0:
            if L[a+dy][b+dx] == "#":
                flag = False
            else:
                if L[a+dy][b +dx] == L[gy][gx]:
                    print(cnt)
                    exit()
                    flag = True
                    visited[a+dy][b +dx] = 1
                    break
        d.append([a+dy][b+dx])
        if not flag:
            for (dy,dx) in li2:
                if 0 <=a+dy<h and 0<=b+dx<w and visited[a+dy][b +dx] ==0:
                    if L[a+dy][b+dx] == "#":
                        flag = False
                    else:
                        flag = True
                        visited[a+dy][b +dx] = 1
                        d.append([a+dy][b+dx])
                        break
            if not flag:
                print(-1)
                exit()
            else:
                cnt +=1
        else:
            if L[a+dy][b +dx] == L[gy][gx]:
                print(cnt)
                exit()
        d.append([a+dy][b+dx])

Submission status: Runtime Error

Solution code:
from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

dx=[0,1,0,-1]
dy=[1,0,-1,0]

def bfs(ans):
  ans[ch-1][cw-1]=0
  qu = deque([])
  qu.append([cw-1,ch-1])
  for i in range(cw-1-2,cw-1+3):
    for j in range(ch-1-2,ch-1+3):
      if 0<=i<w and 0<=j<h:
        if maze[j][i]=="." and (ans[j][i]>ans[ch][cw]+1 or ans[j][i]==-1):
          ans[j][i]=(ans[ch][cw]+1)
          qu.append([i,j])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    if x==dw-1 and y==dh-1:
      break
    count=0
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h and maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):

        qu.append([x+dx[i],y+dy[i]])
        ans[y+dy[i]][x+dx[i]] = ans[y][x]
        if i==3:
          for j in range(-2,3):
            if 0 <= x+dx[i]+j < w and 0 <= y+dy[i]+2 < h and maze[y+dy[i]][x+dx[i]+j]=="." and (ans[y+dy[i]+2][x+dx[i]+j]>ans[y][x]+1 or ans[y+dy[i]+2][x+dx[i]+j]==-1):
              qu.append([x+dx[i]+j,y+dy[i]+2])
              ans[y+dy[i]+2][x+dx[i]+j] = ans[y][x]+1
        elif i==1:
          for j in range(-2,3):
            if 0 <= x+dx[i]+j < w and 0 <= y+dy[i]-2 < h and maze[y+dy[i]][x+dx[i]+j]=="." and (ans[y+dy[i]-2][x+dx[i]+j]>ans[y][x]+1 or ans[y+dy[i]-2][x+dx[i]+j]==-1):
              qu.append([x+dx[i]+j,y+dy[i]-2])
              ans[y+dy[i]-2][x+dx[i]+j] = ans[y][x]+1
              
        elif i==0:
          for j in range(-2,3):
            if 0 <= x+dx[i]+2 < w and 0 <= y+dy[i]+j < h and maze[y+dy[i]][x+dx[i]+j]=="." and (ans[y+dy[i]+2][x+dx[i]+j]>ans[y][x]+1 or ans[y+dy[i]+2][x+dx[i]+j]==-1):
              qu.append([x+dx[i]+2,y+dy[i]+j])
              ans[y+dy[i]+j][x+dx[i]+2] = ans[y][x]+1
        else:
          for j in range(-2,3):
            if 0 <= x+dx[i]-2 < w and 0 <= y+dy[i]+j < h and maze[y+dy[i]+j][x+dx[i]]=="." and (ans[y+dy[i]-2][x+dx[i]+j]>ans[y][x]+1 or ans[y+dy[i]+j-2][x+dx[i]+j]==-1):
              qu.append([x+dx[i]-2,y+dy[i]+j])
              ans[y+dy[i]+j][x+dx[i]-2] = ans[y][x]+1


bfs(ans)
print(ans[dh-1][dw-1])

Submission status: Runtime Error

Solution code:
from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

dx=[0,1,0,-1]
dy=[1,0,-1,0]

def bfs(ans):
  ans[ch-1][cw-1]=0
  qu = deque([])
  qu.append([cw-1,ch-1])
  for i in range(cw-1-2,cw-1+3):
    for j in range(ch-1-2,ch-1+3):
      if 0<=i<w and 0<=j<h:
        if maze[j][i]=="." and (ans[j][i]>ans[ch][cw]+1 or ans[j][i]==-1):
          ans[j][i]=(ans[ch][cw]+1)
          qu.append([i,j])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    if x==dw-1 and y==dh-1:
      break
    count=0
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h and maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):

        qu.append([x+dx[i],y+dy[i]])
        ans[y+dy[i]][x+dx[i]] = ans[y][x]
        if i==0:
          for j in range(-2,3):
            if 0 <= x+dx[i]+j < w and 0 <= y+dy[i]+2 < h and maze[y+dy[i]][x+dx[i]+j]=="." and (ans[y+dy[i]+2][x+dx[i]+j]>ans[y][x]+1 or ans[y+dy[i]+2][x+dx[i]+j]==-1):
              qu.append([x+dx[i]+j,y+dy[i]+2])
              ans[y+dy[i]+2][x+dx[i]+j] = ans[y][x]+1
        elif i==2:
          for j in range(-2,3):
            if 0 <= x+dx[i]+j < w and 0 <= y+dy[i]-2 < h and maze[y+dy[i]][x+dx[i]+j]=="." and (ans[y+dy[i]-2][x+dx[i]+j]>ans[y][x]+1 or ans[y+dy[i]-2][x+dx[i]+j]==-1):
              qu.append([x+dx[i]+j,y+dy[i]-2])
              ans[y+dy[i]-2][x+dx[i]+j] = ans[y][x]+1
              
        elif i==1:
          for j in range(-2,3):
            if 0 <= x+dx[i]+2 < w and 0 <= y+dy[i]+j < h and maze[y+dy[i]][x+dx[i]+j]=="." and (ans[y+dy[i]+2][x+dx[i]+j]>ans[y][x]+1 or ans[y+dy[i]+2][x+dx[i]+j]==-1):
              qu.append([x+dx[i]+2,y+dy[i]+j])
              ans[y+dy[i]+j][x+dx[i]+2] = ans[y][x]+1
        else:
          for j in range(-2,3):
            if 0 <= x+dx[i]-2 < w and 0 <= y+dy[i]+j < h and maze[y+dy[i]+j][x+dx[i]]=="." and (ans[y+dy[i]-2][x+dx[i]+j]>ans[y][x]+1 or ans[y+dy[i]+j-2][x+dx[i]+j]==-1):
              qu.append([x+dx[i]-2,y+dy[i]+j])
              ans[y+dy[i]+j][x+dx[i]-2] = ans[y][x]+1


bfs(ans)
print(ans[dh-1][dw-1])

Submission status: Runtime Error

Solution code:
import copy
(H,W) = map(int,input().split())
(ch,cw) = map(int,input().split())
(dh,dw) = map(int,input().split())
l = []
for i in range(H):
    k=input()
    l.append([k[j] for j in range(W)])
t = copy.deepcopy(l)
s = [[0 for i in range(W)] for j in range(H)]
ans = 0
rn = 0
u = []

cn = "¥"
dn = "¥"

def black(h,w):
    if (ch,cw) == (h,w):
        cn = copy.deepcopy(rn)
    if (dh,dw) == (h,w):
        dn = copy.deepcopy(rn)
    if s[h][w] != 0:
        rrnn = copy.deepcopy(rn)#いる？？
        if [s[h][w],rrnn] not in u:
            u.append([s[h][w],rrnn])
    t[h][w]="#"
    if w<(W-1):
        if t[h][w+1]==".":
            black(h,w+1)
    elif h<(H-1):
        if t[h+1][w]==".":
            black(h+1,w)
    elif w>0:
        if t[h][w-1]==".":
            black(h,w-1)
    elif h>0:
        if t[h-1][w]==".":
            black(h-1,w)

def wrap(h,w):
    rrn = copy.deepcopy(rn)
    for pi in range(-2,3):
        for pj in range(-2,3):
            if 0<=(h+pi) and ((h+pi)<=H and (0<=(w+pj) and (w+pj)<=W)):
                if t[h+pi][w+pj]==".":
                    s[h+pi][w+pj]= rrn


for i in range(H):
    for j in range(W):
        if t[i][j] == ".":
            black(i,j)
            wrap(i,j)
            rn += 1

mat=[cn]

while dn not in mat:
    while s !=[]:
        for x in mat:
            for y in range(rn):
                if [x,y] in s  and y not in mat:
                    mat.append(y)
                    s.remove([x,y])
                elif [y,x] in s  and y not in mat:
                    mat.append(y)
                    s.remove([y,x])
            ans += 1
    print(-1)
print(ans)

Submission status: Runtime Error

Solution code:
import math
from collections import deque
H,W=[int(_) for _ in input().split()]
Ch,Cw=[int(_) for _ in input().split()]
Dh,Dw=[int(_) for _ in input().split()]
chizu=[list(input()) for j in range(H)]
costlist=[[float("inf") for a in range(W)] for b in range(H)]
costlist[Ch-1][Cw-1]=0
willvisit=deque()
willvisit.append((Ch-1,Cw-1))
while willvisit:
    currentpos=willvisit.popleft()
    if currentpos[0]>0:
        if chizu[currentpos[0]-1][currentpos[1]]=="." and costlist[currentpos[0]-1][currentpos[1]]>costlist[currentpos[0]][currentpos[1]]:
            costlist[currentpos[0]-1][currentpos[1]]=costlist[currentpos[0]][currentpos[1]]
            willvisit.append((currentpos[0]-1,currentpos[1]))
    if currentpos[1]>0:
        if chizu[currentpos[0]][currentpos[1]-1]=="." and costlist[currentpos[0]][currentpos[1]-1]>costlist[currentpos[0]][currentpos[1]]:
            costlist[currentpos[0]][currentpos[1]-1]=costlist[currentpos[0]][currentpos[1]]
            willvisit.append((currentpos[0],currentpos[1]-1))
    if currentpos[0]<H-1:
        if chizu[currentpos[0]+1][currentpos[1]]=="." and costlist[currentpos[0]+1][currentpos[1]]>costlist[currentpos[0]][currentpos[1]]:
            costlist[currentpos[0]+1][currentpos[1]]=costlist[currentpos[0]][currentpos[1]]
            willvisit.append((currentpos[0],currentpos[1]+1))
    if currentpos[1]<W-1:
        if  chizu[currentpos[0]][currentpos[1]+1]=="." and costlist[currentpos[0]][currentpos[1]+1]>costlist[currentpos[0]][currentpos[1]]:
            costlist[currentpos[0]][currentpos[1]+1]=costlist[currentpos[0]][currentpos[1]]
            willvisit.append((currentpos[0],currentpos[1]+1))
    for a in range(25):
        dx=(a//5)-2
        dy=(a%5)-2
        ygoto=currentpos[0]+dy
        xgoto=currentpos[1]+dx
        if 0<=ygoto<=H-1 and 0<=xgoto<=W-1:
            if chizu[ygoto][xgoto]==".":
                if costlist[ygoto][xgoto]>costlist[currentpos[0]][currentpos[1]]+1:
                    costlist[ygoto][xgoto]=costlist[currentpos[0]][currentpos[1]]+1
                    willvisit.append((ygoto,xgoto))
if costlist[Dh-1][Dw-1]==float("inf"):
    print(-1)
else:
    print(costlist[Dh-1][Dw-1])