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

Solution (Python):
from collections import deque

H,W = map(int,input().split())
C_pos=list(map(lambda x:int(x)-1,input().split()))
D_pos=list(map(lambda x:int(x)-1,input().split()))
Grid=[[c for c in input()] for _ in range(H)]

Dist=[[float("inf")]*W for _ in range(H)]

DX=[0,0,1,-1]

Q=deque()
Q.append((C_pos[0],C_pos[1]))
Dist[C_pos[0]][C_pos[1]]=0

while Q:
    cx,cy = Q.pop()

    for dx,dy in zip(DX,reversed(DX)):
        nx=cx+dx
        ny=cy+dy

        if 0<=nx<H and 0<=ny<W and Grid[nx][ny]=="." and Dist[nx][ny]>Dist[cx][cy]:
            Dist[nx][ny]=Dist[cx][cy]
            Q.append((nx,ny))


    for dx in range(-2,3):
        for dy in range(-2,3):
            nx=cx+dx
            ny=cy+dy
            if dx==0 and dy==0:
                continue

            if 0<=nx<H and 0<=ny<W and Grid[nx][ny]=="." and Dist[nx][ny]==float("inf"):
                Dist[nx][ny]=Dist[cx][cy]+1
                Q.appendleft((nx,ny))


ans=Dist[D_pos[0]][D_pos[1]]
if ans==float("inf"):
    print(-1)
else:
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(500000)

import sys
def input():
    return sys.stdin.readline()[:-1]

H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
S = [list(input()) for i in range(H)]
 
from collections import deque
 
q = deque([(CH-1, CW-1)])
 
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
warp = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
        (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),
        (0, -2), (0, -1), (0, 1), (0, 2), 
        (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),
        (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            S[i][j] = 10**7
S[CH-1][CW-1] = 0

while q:
    h, w = q.popleft()
    for wh, ww in warp:
        if 0 <= h+wh < H and 0 <= w+ww < W and S[h+wh][w+ww] != "
            if (wh, ww) in directions:
                if S[h+wh][w+ww] > S[h][w]:
                    S[h+wh][w+ww] = S[h][w]
                    q.appendleft((h+wh, w+ww))
            else:
                if S[h+wh][w+ww] > S[h][w] + 1:
                    S[h+wh][w+ww] = S[h][w] + 1
                    q.append((h+wh, w+ww))

if S[DH-1][DW-1] == 10**7:
    print(-1)
else:
    print(S[DH-1][DW-1])

Solution (Python):
from collections import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
S = ["
v = [[10 ** 6]*(w+2) for _ in range(h+2)]
v[ch][cw] = 0
Q = deque([(ch,cw)])
while Q :
    y,x = Q.pop()
    for i,j in [(0,1),(1,0),(-1,0),(0,-1)] :
        if S[y+i][x+j] == "." and v[y+i][x+j] > v[y][x]:
            v[y+i][x+j] = v[y][x]
            Q.append((y+i,x+j))
    for i in range(-2,3) :
        for j in range(-2,3) :
            if i == j == 0 :
                continue
            elif 1 <= y+i <= h and 1 <= x+j <= w and S[y+i][x+j] == "." and v[y+i][x+j] > v[y][x] + 1 :
                v[y+i][x+j] = v[y][x] + 1
                Q.appendleft((y+i,x+j))
ans = v[dh][dw]
if ans == 10 ** 6 :
    print(-1)
else :
    print(ans)

Solution (Python):
import sys


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['
    for _ in range(H):
        S += ['
    S += ['
    H += 2
    W += 2
    now = ch*W + cw
    goal = dh*W + dw
    q = [now]
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[now] = 0

    while q:
        same_area = []
        while q:
            x = q.pop()
            same_area.append(x)
            for d in [-W, -1, 1, W]:
                if S[x+d] == '.' and dist[x+d] > dist[x]:
                    q.append(x+d)
                    dist[x+d] = dist[x]
        
        for x in same_area:
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in range(-2, 3):
                    xx = x + dy + dx
                    if 0 <= xx < W*H and dist[xx] > dist[x] and S[xx] == '.':
                        q.append(xx)
                        dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W = mapint()
ch, cw = mapint()
dh, dw = mapint()
maze = [list(input()) for _ in range(H)]

dirc = set([(-1, 0), (1, 0), (0, -1), (0, 1)])
from collections import deque
from heapq import heappop, heappush
Q = [(0, (ch-1)*(10**4)+cw-1)]

dist = [[10**18]*W for _ in range(H)]
dist[ch-1][cw-1] = 0
ans = 10**18
while Q:
    d, yx = heappop(Q)
    y, x = divmod(yx, 10**4)
    if d>dist[y][x]:
        continue
    dist[y][x] = d
    if y==dh-1 and x==dw-1:
        ans = d
        break
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            ny, nx = y+dy, x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if maze[ny][nx]=='
                continue
            if (dy, dx) in dirc:
                if dist[ny][nx]>d:
                    dist[ny][nx] = d
                    heappush(Q, (d, ny*(10**4)+nx))
            else:
                if dist[ny][nx]>d+1:
                    dist[ny][nx] = d+1
                    heappush(Q, (d+1, ny*(10**4)+nx))
if ans>=10**17:
    print(-1)
else:
    print(ans)

Solution (Python):

MOD = 10 ** 9 + 7
INFI = 10**10

import math
from collections import deque
import itertools
import heapq

from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint




def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default




def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    
    h,w= map(int, input().split())
    cx,cy = map(int, input().split())
    dx,dy = map(int, input().split())
    s=[]
    s.append(list("
    s.append(list("
    for i in range(h):
        temp=input()
        temp="
        s.append(list(temp))
    s.append(list("
    s.append(list("



    visited = [[0 for i in range(w+4)] for _ in range(h+4)]
    warpvisited = [[0 for i in range(w + 4)] for _ in range(h + 4)]
    warp = [[INFI for i in range(w+4)] for _ in range(h+4)]
    visited[cx+1][cy+1]=1
    warp[cx+1][cy+1]=0

    queue = deque([])

    warpdire=[[-2,-2],[-1,-2],[0,-2],[1,-2],[2,-2],
           [-2,-1],[-1,-1],[1,-1],[2,-1],
           [-2,0],[2,0],
           [-2,1],[-1,1],[1,1],[2,1],
           [-2,2],[-1,2],[0,2],[1,2],[2,2],
              [0,-1],[-1,0],[1,0],[0,1]]
    walkdire=[[0,-1],[-1,0],[1,0],[0,1]]

    warpvisited = [[0 for i in range(w + 4)] for _ in range(h + 4)]
    walkvisited = [[0 for i in range(w + 4)] for _ in range(h + 4)]
    rekkyo=[]
    rekkyo2=[]
    nowx = cx + 1
    nowy = cy + 1
    def walkloop(nowx,nowy):
        walkvisited[nowx][nowy]=1
        rekkyo.append([nowx,nowy])
        for i in walkdire:
            if s[nowx + i[0]][nowy + i[1]] == "." and walkvisited[nowx + i[0]][nowy + i[1]] == 0:
                queue.append([nowx + i[0], nowy + i[1]])
                warp[nowx + i[0]][nowy + i[1]] = min(warp[nowx][nowy], warp[nowx + i[0]][nowy + i[1]])
                visited[nowx + i[0]][nowy + i[1]] = 1
                walkvisited[nowx + i[0]][nowy + i[1]] = 1
                rekkyo.append([nowx+i[0],nowy+i[1]])
        while queue:
            if len(queue) <= 0:
                return
            now = queue.popleft()
            nowx = now[0]
            nowy = now[1]


            for i in walkdire:
                if s[nowx + i[0]][nowy + i[1]] == "." and walkvisited[nowx + i[0]][nowy + i[1]] == 0:
                    queue.append([nowx + i[0], nowy + i[1]])
                    warp[nowx + i[0]][nowy + i[1]] = min(warp[nowx][nowy], warp[nowx + i[0]][nowy + i[1]])
                    visited[nowx + i[0]][nowy + i[1]] = 1
                    walkvisited[nowx + i[0]][nowy + i[1]] = 1
                    rekkyo.append([nowx + i[0], nowy + i[1]])

        return
    def warploop(nowx,nowy,cost):
        for i in warpdire:
            if s[nowx + i[0]][nowy + i[1]] == "." and warp[nowx + i[0]][nowy + i[1]]>cost:

                warp[nowx + i[0]][nowy + i[1]] = min(warp[nowx][nowy]+1, warp[nowx + i[0]][nowy + i[1]])
                visited[nowx + i[0]][nowy + i[1]] = 1
                warpvisited[nowx + i[0]][nowy + i[1]] = 1
                rekkyo2.append([nowx+i[0],nowy+i[1]])
        return
    cost=0
    walkloop(cx + 1, cy + 1)
    cost += 1

    while True:
        for i in rekkyo:
            warploop(i[0],i[1],cost)
        rekkyo=[]
 
        for i in rekkyo2:
            walkloop(i[0],i[1])
        rekkyo2=[]
   
        if len(rekkyo)==0:
            break

        cost+=1


    if visited[dx+1][dy+1]==0:
        print("-1")
    else:
        print(warp[dx+1][dy+1])


 
 
 




if __name__ == "__main__":

    main()

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter


from heapq import heappush, heappop

input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

H, W = rl()
C = rl()
D = rl()
M = []
for i in range(H):
	s = rs()
	M.append(s)

start = tuple([C[0]-1, C[1]-1])
end = tuple([D[0]-1, D[1]-1])

queue = deque()
queue.append((start, 0))
visited = [[float('inf')]*W for _ in range(H)]
visited[start[0]][start[1]] = 0

ds = [(1,0),(-1,0),(0,1),(0,-1)]
while queue:
	n, d = queue.popleft()
	if n == end:
		print(d)
		exit()
	i, j = n
	if visited[i][j] != d:
		continue
	nd = d
	for di, dj in ds:
		ni, nj = i+di, j+dj
		if not (0 <= ni < H and 0 <= nj < W): continue
		if M[ni][nj] == '
		if nd < visited[ni][nj]:
			queue.appendleft(((ni,nj), nd))
			visited[ni][nj] = nd
	nd = d+1
	for di in range(-2, 3):
		for dj in range(-2, 3):
			if (di, dj) == (0,0): continue
			ni, nj = i+di, j+dj
			if not (0 <= ni < H and 0 <= nj < W): continue
			if M[ni][nj] == '
			if nd < visited[ni][nj]:
				queue.append(((ni,nj), nd))
				visited[ni][nj] = nd
print(-1)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)

walks = [(-1,0),(1,0),(0,1),(0,-1)]
magics = []
for i in range(-2,3):
    for j in range(-2,3):
        if i==j==0:continue
        if (i,j) not in walks:
            magics.append((i,j))

INF = 1 << 50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = deque([])
q.appendleft((ch-1,cw-1,0))
while len(q)>0:
    h,w,cnt = q.popleft()
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    for dh, dw in walks:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.appendleft((hn, wn, cnt))
    for dh, dw in magics:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.append((hn, wn, cnt+1))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():
    h, w = LI()
    ch, cw = LI_()
    dh, dw = LI_()
    q = deque()
    s = [None] * h
    c = [None] * h
    for i in range(h):
        s[i] = S()
        c[i] = [inf] * w
    q.append((ch, cw))
    c[ch][cw] = 0
    while q:
        nh, nw = q.popleft()
        now = c[nh][nw]
        for mh, mw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
            mh += nh
            mw += nw
            if 0 <= mh < h and 0 <= mw < w and c[mh][mw] > now and s[mh][mw] == ".":
                c[mh][mw] = now
                q.appendleft((mh, mw))
        for i in range(-2, 3):
            i += nh
            for j in range(-2, 3):
                j += nw
                if 0 <= i < h and 0 <= j < w and c[i][j] > now + 1 and s[i][j] == ".":
                    c[i][j] = now + 1
                    q.append((i, j))
    print(-1 if c[dh][dw] == inf else c[dh][dw])
    return



if __name__ == '__main__':
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
graph = [0] + [0] * h
dist = [0] + [0] * h
for i in range(h):
    graph[i + 1] = [0] + list(input().strip())
    dist[i + 1] = [0] + [-1] * w

from collections import deque

def can_move(graph, dist, next_h, next_w):
    if not ((1 <= next_h <= h) and (1 <= next_w <= w)):
        return False
    if graph[next_h][next_w] == '
        return False
    return True


def bfs(graph, queue, dist):
    part = set()
    while queue:
        current_h, current_w = queue.popleft()

        
        for dh, dw in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            next_h, next_w = current_h + dh, current_w + dw
            if not can_move(graph, dist, next_h, next_w):
                continue
            
            
            
            if dist[next_h][next_w] == -1 or dist[next_h][next_w] > dist[current_h][current_w]:
                dist[next_h][next_w] = dist[current_h][current_w]
                queue.appendleft((next_h, next_w))

        
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                next_h, next_w = current_h + dh, current_w + dw
                if not can_move(graph, dist, next_h, next_w):
                    continue
                if dist[next_h][next_w] != -1:
                    continue
                dist[next_h][next_w] = dist[current_h][current_w] + 1
                queue.append((next_h, next_w))

queue = deque([(ch, cw)])
dist[ch][cw] = 0
bfs(graph, queue, dist)
print(dist[dh][dw])

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter


from heapq import heappush, heappop

input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

H, W = rl()
C = rl()
D = rl()
M = []
for i in range(H):
	s = rs()
	M.append(s)

start = tuple([C[0]-1, C[1]-1])
end = tuple([D[0]-1, D[1]-1])

queue = deque()
queue.append((start, 0))
visited = defaultdict(lambda: float('inf'))
visited[start] = 0

ds = [(1,0),(-1,0),(0,1),(0,-1)]
while queue:
	n, d = queue.popleft()
	if n == end:
		print(d)
		exit()
	if visited[n] != d:
		continue
	i, j = n
	nd = d
	for di, dj in ds:
		ni, nj = i+di, j+dj
		if not (0 <= ni < H and 0 <= nj < W): continue
		if M[ni][nj] == '
		if nd < visited[(ni,nj)]:
			queue.appendleft(((ni,nj), nd))
			visited[(ni,nj)] = nd
	nd = d+1
	for di in range(-2, 3):
		for dj in range(-2, 3):
			if (di, dj) == (0,0): continue
			ni, nj = i+di, j+dj
			if not (0 <= ni < H and 0 <= nj < W): continue
			if M[ni][nj] == '
			if nd < visited[(ni,nj)]:
				queue.append(((ni,nj), nd))
				visited[(ni,nj)] = nd
print(-1)

Solution (Python):
from collections import deque

def bfs():
    
    wpCnt = [[int(10**10)] * m for i in range(n)]

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

    sx = Cm-1
    sy = Cn-1

    que = deque([])
    que.append((sy, sx))
    wpCnt[sy][sx] = 0

    
    while que:
        
        p = que.popleft()
        
        for i in range(4):
            
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "
                
                wpCnt[nx][ny] = wpCnt[p[0]][p[1]]
                que.appendleft((nx, ny))

        
        for i in range(-2,3):
            for j in range(-2,3):
                
                nxw = p[0] + i
                nyw = p[1] + j

                
                if 0 <= nxw < n and 0 <= nyw < m and maze[nxw][nyw] != "
                    
                    
                    wpCnt[nxw][nyw] = wpCnt[p[0]][p[1]] + 1
                    que.append((nxw, nyw))
    return wpCnt

n, m = map(int, input().split())
Cn,Cm = map(int, input().split())
Dn,Dm = map(int, input().split())
maze = [list(input()) for _ in range(n)]

ans = bfs()


if ans[Dn-1][Dm-1] == 10**10:
    print(-1)
else:
    print(ans[Dn-1][Dm-1])

Solution (Python):
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
slist = [input() for i in range(h)]

if ch == dh and dw == cw:
    print(0)
    exit()

que = deque()
memo_que = deque()
que.append([ch - 1, cw - 1, 0])
memo = [[False for i in range(w)] for j in range(h)]
memo[ch - 1][cw - 1] = True

while len(que) != 0:
    
    while len(que) != 0:
        sh, sw, count = que.popleft()
        memo_que.append([sh, sw, count])
        
        for ph, pw in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
            if 0 <= sh + ph < h and 0 <= sw + pw < w:
                if sh + ph == dh - 1 and sw + pw == dw - 1:
                    print(count)
                    exit()
                if memo[ph + sh][pw + sw]:
                    continue
                if slist[sh + ph][sw + pw] == ".":
                    que.append([sh + ph, sw + pw, count])
                    memo[ph + sh][pw + sw] = True
                    memo_que.append([sh + ph, sw + pw, count])

    for sh, sw, count in memo_que:
        
        for ph in range(-2, 3):
            for pw in range(-2, 3):
                if 0 <= sh + ph < h and 0 <= sw + pw < w:
                    if sh + ph == dh - 1 and sw + pw == dw - 1:
                        print(count + 1)
                        exit()
                    if memo[ph + sh][pw + sw]:
                        continue
                    if slist[sh + ph][sw + pw] == ".":
                        que.append([sh + ph, sw + pw, count + 1])
                        memo[ph + sh][pw + sw] = True
    memo_que.clear()
print(-1)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():
    h, w = LI()
    ch, cw = LI_()
    dh, dw = LI_()
    s = [None] * h
    c = [None] * h
    for i in range(h):
        s[i] = S()
        c[i] = [inf] * w
    q = deque()
    q.append((ch, cw))
    c[ch][cw] = 0
    nq = deque()
    mv = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    mij = [(i, j) for i in range(-2, 3) for j in range(-2, 3)]
    while 1:
        while q:
            nh, nw = q.popleft()
            now = c[nh][nw]
            nq.append((nh, nw))
            for mh, mw in mv:
                mh += nh
                mw += nw
                if 0 <= mh < h and 0 <= mw < w and c[mh][mw] > now and s[mh][mw] == ".":
                    c[mh][mw] = now
                    q.appendleft((mh, mw))
        while nq:
            nh, nw = nq.popleft()
            now = c[nh][nw]
            for mi, mj in mij:
                mi += nh
                mj += nw
                if 0 <= mi < h and 0 <= mj < w and c[mi][mj] > now + 1 and s[mi][mj] == ".":
                    c[mi][mj] = now + 1
                    q.append((mi, mj))
        if len(q) == 0:
            break
    print(-1 if c[dh][dw] == inf else c[dh][dw])
    return



if __name__ == '__main__':
    solve()

Solution (Python):
class Grid:
    def __init__(self, H, W, grid, road_wall=(".", "
        self.road, self.wall = road_wall
        self.H = H
        self.W = W
        self.grid = grid
        self.parent = [[-1] * self.W for _ in range(self.H)]
        self.move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     
        self.move2 = dict()
        self.move2[(1,0)] = [(2,-1),(2,0),(2,1),(2,2),(1,1)]
        self.move2[(-1,0)] = [(-2,-1),(-2,0),(-2,1),(-2,-2),(-1,-1)]
        self.move2[(0,1)] = [(1,2),(0,2),(-1,2),(-2,2),(-1,1)]
        self.move2[(0,-1)] = [(1,-2),(0,-2),(-1,-2),(2,-2),(1,-1)]

    def bfs(self, start=(0,0), goal=-3, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if save:
            parent = self.parent
        else:
            parent = [[-1] * self.W for _ in range(self.H)]
        p, t = start, time
        parent[p[0]][p[1]] = -2
        next_set = deque([(p, t)])
        broken_set = deque([])
        while next_set:
            while next_set:
                p, t = next_set.popleft()
                h, w = p
                for dh, dw in self.move:
                    nh, nw = (h + dh, w + dw)
                    if nh < 0 or nh >= self.H or nw < 0 or nw >= self.W:
                        continue
                    if parent[nh][nw] != -1:
                        continue
                    if self.grid[nh][nw] == self.wall:         
                        for dh2, dw2 in self.move2[(dh,dw)]:
                            r = (h + dh2, w + dw2)
                            broken_set.append((r, t))
                        continue
                    if (nh, nw) == goal:
                        return t
                    
                    
                    
                    parent[nh][nw] = p
                    next_set.append(((nh, nw), t))
            while broken_set:
                q, t = broken_set.popleft()
                nh, nw = q
                if nh < 0 or nh >= self.H or nw < 0 or nw >= self.W:
                    continue
                if parent[nh][nw] != -1:
                    continue
                if self.grid[nh][nw] == self.wall:  
                    continue
                if (nh, nw) == goal:
                    return t + 1
                parent[nh][nw] = 1
                next_set.append((q, t+1))
        return -1

    def debug(self, start, goal, p, t):
        player = p
        debug_grid = list(list(self.grid[h]) for h in range(self.H))
        if start != (None, None):
            debug_grid[start[0]][start[1]] = "S"
        if goal != -3:
            debug_grid[goal[0]][goal[1]] = "G"
        debug_grid[player[0]][player[1]] = "P"
        print("~~~~~~~~~ t = " + str(t + 1) + "  ~~~~~~~~")
        for debug_h in range(self.H):
            print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W)))




from collections import deque
import sys
input = sys.stdin.readline



road, wall = ".", "

H, W = map(int,input().split())                
x, y = map(int, input().split())
start = (x-1,y-1)
x, y = map(int, input().split())
goal = (x-1,y-1)
grid = []
for h in range(H):
    grid.append(input().rstrip())

g = Grid(H, W, grid, (road, wall))
res = g.bfs(start=start, goal=goal)
print(res)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [W for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        
    ans = 0
    q = set([(Dh, Dw)])
    while True:
        nq = set()
        while q:
            q_ = set()
            for h, w in q:
                
                if h == Ch and w == Cw:
                    print(ans)
                    return True
                M[h][w] = '
                nq.add((h, w))
                for dh, dw in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    if 0 <= h+dh < H and 0 <= w+dw < W:
                        if M[h+dh][w+dw] == '.':
                            q_.add((h+dh, w+dw))
                            M[h+dh][w+dw] = '
            q = q_

        if nq:
            for h, w in nq:
                for dh in range(-2, 3):
                    for dw in range(-2, 3):
                        if 0 <= h+dh < H and 0 <= w+dw < W:
                            if M[h+dh][w+dw] == '.':
                                q.add((h+dh, w+dw))
        
        
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

if __name__ == '__main__':
    main()

Solution (Python):
h,w = map(int, input().split())
ch, cw = map(int, input().split())
ch -= 1
cw -= 1
dh,dw = map(int, input().split())
dh -= 1
dw -= 1

def trans(s):
    res = []
    for i in s:
        if i == '.':
            res.append(-1)
        else:
            res.append(-2)
    return res

def move(x,y,dq,dq_next):
    for ix,iy in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
        if ix > h-1 or ix < 0 or iy > w-1 or iy < 0:
            continue
        if (m[ix][iy] == -1) or (m[ix][iy] > m[x][y]):
            m[ix][iy] = m[x][y]
            dq.append((ix, iy))
    for ix, iy in [(x-2, y-2), (x-2, y-1), (x-2, y), (x-2, y+1), (x-2, y+2),
                        (x-1, y-2), (x-1, y-1), (x-1, y+1), (x-1, y+2),
                        (x, y-2), (x, y+2),
                        (x+1, y-2), (x+1, y-1), (x+1, y+1), (x+1, y+2),
                        (x+2, y-2), (x+2, y-1), (x+2, y), (x+2, y+1), (x+2, y+2)]:
        if ix > h-1 or ix < 0 or iy > w-1 or iy < 0:
            continue
        if m[ix][iy] == -1:
            m[ix][iy] = m[x][y] + 1
            dq_next.append((ix, iy))
            
m = [trans(input()) for _ in range(h)]

from collections import deque

m[ch][cw] = 0

def main():
    dq = deque()
    dq_next = deque()
    dq.append((ch,cw))
    while True:
        while len(dq)>0:
            xx, yy = dq.popleft()
            if xx == dh and yy == dw:
                return m[xx][yy]
            move(xx, yy, dq, dq_next)
        if len(dq_next) > 0:
            dq = dq_next.copy()
            dq_next = deque()
        else:
            return -1
          
print(main())