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):
import copy
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

S = []
for i in range(h):
    S.append(list(input()))


def by_walk(stack):
    walk_point = copy.copy(stack)
    while stack != []:
        temp = []
        for i, j in stack:
            warp_counter = S[i][j]
            next_points = [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]
            for next_point in next_points:
                next_h, next_w = next_point
                if next_h >= 0 and next_h < h and next_w >= 0 and next_w < w:
                    if S[next_h][next_w] ==".":
                        S[next_h][next_w] = warp_counter
                        temp.append(next_point)
                        walk_point.append(next_point)
        stack = temp
    return walk_point

def warp(stack):
    warp_point = []
    for i, j in stack:
        warp_counter = S[i][j]
        for shift_i in range(-2, 3):
            for shift_j in range(-2, 3):
                new_i = i + shift_i
                new_j = j + shift_j
                if not(new_i == i and new_j == j):
                    if new_i >= 0 and new_i < h and new_j >= 0 and new_j < w:
                        if S[new_i][new_j] == ".":
                            S[new_i][new_j] = warp_counter + 1
                            warp_point.append((new_i, new_j))
    return warp_point

stack = [(ch, cw)]
S[ch][cw] = 0
"""
ans = by_walk(stack)
print(ans)
ans = warp(ans)
print(*S, sep="\n")
print(ans)
"""
while stack != []:
    stack = by_walk(stack)
    
    
    if S[dh][dw] != ".":
        print(S[dh][dw])
        break
    stack = warp(stack)
    
    
    if S[dh][dw] != ".":
        print(S[dh][dw])
        break
else:
    print(-1)

Solution (Python):
from heapq import heapify, heappop, heappush
inpl = lambda: list(map(int,input().split()))
H, W = inpl()
sh, sw = inpl()
start = (sh-1, sw-1)
gh, gw = inpl()
goal = (gh-1, gw-1)
S = [input() for _ in range(H)]

count = [[-1]*W for _ in range(H)]
count[start[0]][start[1]] = 0
q = [(0, start)]
while q:
    d, p = heappop(q)
    if p == goal:
        print(d)
        exit()
    h, w = p
    if d > count[h][w]:
        continue
    for dh, dw in ((1,0), (-1,0), (0,1), (0,-1)):
        nh, nw = h+dh, w+dw
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and (count[nh][nw] < 0 or count[nh][nw] > d):
            count[nh][nw] = d
            heappush(q, (d, (nh, nw)))
    for dh in range(-2,3):
        for dw in range(-2,3):
            nh, nw = h+dh, w+dw
            if (dh,dw) != (0,0) and 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and count[nh][nw] < 0:
                count[nh][nw] = d+1
                heappush(q, (d+1, (nh, nw)))
print(-1)

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

from collections import deque
import itertools

h,w = map(int,readline().split())
cx,cy = map(int,readline().split())
gx,gy = map(int,readline().split())
cx -= 1
cy -= 1
grid = [readline().rstrip() for i in range(h)]

dist = [[INF]*w for i in range(h)]
dist[cx][cy] = 0

l2 = list(itertools.product([-2,-1,0,1,2],repeat = 2))
l1 = [(-1,0),(1,0),(0,-1),(0,1)]
q1 = deque([(cx,cy)])
q2 = deque([(cx,cy)])

while q1 or q2:
    if q1:
        x,y = q1.popleft()
        for dy,dx in l1:
            ny,nx = y+dy, x+dx
            if not (0 <= ny < w and 0 <= nx < h):
                continue
            if grid[nx][ny] == '
                continue
            if dist[nx][ny] != INF:
                continue
            if dist[nx][ny] > dist[x][y]:
                dist[nx][ny] = dist[x][y]
                q1.append((nx,ny))
                q2.append((nx,ny))
    else:
        x,y = q2.popleft()
        for dy,dx in l2:
            ny,nx = y+dy, x+dx
            if not (0 <= ny < w and 0 <= nx < h):
                continue
            if grid[nx][ny] == '
                continue
            if dist[nx][ny] != INF:
                continue
            if dist[nx][ny] > dist[x][y]+1:
                dist[nx][ny] = dist[x][y]+1
                q1.append((nx,ny))
                q2.append((nx,ny))

print(dist[gx-1][gy-1] if dist[gx-1][gy-1] != INF else -1)

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    dxys = [(-1,0), (1,0), (0,-1), (0,1)]

    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Sss = ['

    Ch, Cw, Dh, Dw = Ch+1, Cw+1, Dh+1, Dw+1

    usedss = [[0]*(W+4) for _ in range(H+4)]
    for x in range(H+4):
        for y in range(W+4):
            if Sss[x][y] == '
                usedss[x][y] = 1

    ans = 0
    vs = set([(Ch, Cw)])
    vNews = set([(Ch, Cw)])
    usedss[Ch][Cw] = 1
    while True:
        while vs:
            v2s = set()
            for x, y in vs:
                for dx, dy in dxys:
                    x2, y2 = x+dx, y+dy
                    if usedss[x2][y2]: continue
                    v2s.add((x2, y2))
                    vNews.add((x2, y2))
                    usedss[x2][y2] = 1
            vs = v2s

        if usedss[Dh][Dw]:
            print(ans)
            break

        if not vNews:
            print(-1)
            break

        vs = set()
        for x, y in vNews:
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    x2, y2 = x+dx, y+dy
                    if usedss[x2][y2]: continue
                    vs.add((x2, y2))
                    usedss[x2][y2] = 1

        ans += 1
        vNews = set(vs)


solve()

Solution (Python):
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.append(["
S.append(["
S.append(["

cnt = [[float("inf")] * (W + 4) for _ in range(H + 4)]
cnt[Ch][Cw] = 0

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

from collections import deque

def serch(Sh, Sw, count):
    q = [(Sh, Sw)]
    done = [(Sh, Sw)]
    while q:
        qq = []
        for h, w in q:
            for dy, dx in zip(DY, DX):
                nh = h + dy
                nw = w + dx

                if S[nh][nw] == "." and cnt[nh][nw] > count:
                    qq.append((nh, nw))
                    done.append((nh, nw))
                    cnt[nh][nw] = count
        q = qq
    
    return done

DONE = serch(Ch, Cw, 0)
ans = 1
while DONE:
    DDONE = []
    for h, w in DONE:
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                nh = h + dy
                nw = w + dx

                if S[nh][nw] == "." and cnt[nh][nw] > ans:
                    cnt[nh][nw] = ans
                    DDONE += serch(nh, nw, ans)
    
    ans += 1
    DONE = DDONE

if cnt[Dh][Dw] == float("inf"):
    print(-1)
else:
    print(cnt[Dh][Dw])

Solution (Python):
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def solve(dist, start, goal):
    H,W = len(dist),len(dist[0])

    q = [start]
    dist[start[0]][start[1]] = 0
    cnt = 0
    while q:
        nq = []
        while q:
            x,y = q.pop()
            if (x,y) == goal:
                return cnt
            if dist[x][y] < cnt:
                continue
            for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
                nx,ny = x+dx,y+dy
                if 0<=ny<W and 0<=nx<H and dist[nx][ny] > cnt:
                    dist[nx][ny] = cnt
                    q.append((nx,ny))
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx,ny = x+dx,y+dy
                    if 0<=ny<W and 0<=nx<H and dist[nx][ny] > cnt+1:
                        dist[nx][ny] = cnt+1
                        nq.append((nx,ny))
        q = nq
        cnt += 1
    return -1




if __name__ == '__main__':
    H,W = map(int,readline().split())
    start = tuple(map(lambda i:int(i)-1,readline().split()))
    goal = tuple(map(lambda i:int(i)-1,readline().split()))

    dist = [[10**7 if c=='.' else -1 for c in t.decode()] for t in read().split()]

    print(solve(dist,start,goal))

Solution (Python):

import heapq

h, w = map(int, input().split())
cx, cy = map(lambda x: int(x) - 1, input().split())
dx, dy = map(lambda x: int(x) - 1, input().split())
s = [input() for _ in range(h)]
c = [[10**6] * w for _ in range(h)]


def bfs():
    d = ((1, 0), (-1, 0), (0, 1), (0, -1))
    d2 = (
        (-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),
    )
    hp = []

    heapq.heappush(hp, (0, (cx, cy)))
    c[cx][cy] = 0

    while hp:
        cp, (
            x,
            y,
        ) = heapq.heappop(hp)
        if (x, y) == (dx, dy):
            c[x][y] = cp
            break
        for i in range(4):
            nx = x + d[i][0]
            ny = y + d[i][1]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "
                    ny] > cp:
                heapq.heappush(hp, (cp, (nx, ny)))
                c[nx][ny] = cp
        cp += 1
        for i in range(20):
            nx = x + d2[i][0]
            ny = y + d2[i][1]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "
                    ny] > cp:
                c[nx][ny] = cp
                heapq.heappush(hp, (cp, (nx, ny)))

    return c[dx][dy] if c[dx][dy] < 10**6 else -1


print(bfs())

Solution (Python):
from collections import deque
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
    m = [[0]*(w+4)]
    m.append([0]*(w+4))
    for i in range(h):
        s = input()
        temp = [0,0]
        for j in s:
            if j == ".":
                temp.append(1)
            else:
                temp.append(0)
        temp.append(0)
        temp.append(0)
        m.append(temp)
    m.append([0]*(w+4))
    m.append([0]*(w+4))

    t = [[1000000]*(w+4) for _ in range(h+4)]


    queue = deque([(ch,cw,0)])
    t[ch][cw] = 0
    
    while(len(queue) > 0):
        q = queue.popleft()
        nh = q[0]
        nw = q[1]
        dir = [(1,0),(-1,0),(0,1),(0,-1)]
        
        for d in dir:
            if m[nh + d[0]][nw + d[1]] == 1 and t[nh + d[0]][nw + d[1]] > q[2]:
                queue.appendleft((nh + d[0] , nw + d[1], q[2]))
                t[nh + d[0]][nw + d[1]] = q[2]

        dir = [(1,1),(-1,1),(-1,-1),(1,-1),(-2,2),(-1,2),(0,2),(1,2),(2,2),(-2,1),(2,1),(-2,0),(2,0),(-2,-1),(2,-1),(-2,-2),(-1,-2),(0,-2),(1,-2),(2,-2)]

        for d in dir:
            if m[nh + d[0]][nw + d[1]] == 1 and t[nh + d[0]][nw + d[1]] > q[2]+1:
                queue.append((nh + d[0] , nw + d[1], q[2] + 1))
                t[nh + d[0]][nw + d[1]] = q[2]+1
        

    print(t[dh][dw] if t[dh][dw] != 1000000 else -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)

dist = defaultdict(lambda: float('inf'))
def dijkstra(start, end):
	dist[start] = 0
	heap = []
	heappush(heap, (0, start))
	while heap:
		d, n = heappop(heap)
		if n == end:
			return d
		if dist[n] != d:
			continue
		edges = get_edges(n)
		for nn, ed in edges:
			nd = d + ed
			if dist[nn] > nd:
				dist[nn] = nd
				heappush(heap, (nd, nn))
	return -1

def get_edges(n):
	i, j = n
	edges = []
	if M[i][j] == '
	for di in range(-2, +3):
		for dj in range(-2, +3):
			ni, nj = i+di, j+dj
			if di == 0 and dj == 0: continue
			if not(0 <= ni < H and 0 <= nj < W): continue
			if M[ni][nj] == '
			if (di, dj) in [(1,0),(-1,0),(0,1),(0,-1)]:
				edges.append(((ni, nj), 0))
			else:
				edges.append(((ni, nj), 1))
	return edges

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])
d = dijkstra(start, end)
print(d)

Solution (Python):

import sys
input = sys.stdin.readline
from collections import deque
H,W = map(int,input().split())
Sh,Sw = map(int,input().split())
Sh -= 1
Sw -= 1
Gh,Gw = map(int,input().split())
Gh -= 1
Gw -= 1
S = [list(input()) for _ in range(H)]
D = [[-1 for _ in range(W)] for _ in range(H)]
D[Sh][Sw] = -1


walk = [(1,0),(-1,0),(0,1),(0,-1)]
warp = [(x,y) for x in range(-2,3) for y in range(-2,3) if abs(x) + abs(y) > 1]
def validPosition(h,w):
	return 0 <= h and h < H and 0 <= w and w < W

search = [(0, Sh, Sw)]
V = [[False for _ in range(W)] for _ in range(H)]
while D[Gh][Gw] == -1:
	walked = []
	
	while len(search) > 0:
		(d, h, w) = search.pop()
		if D[h][w] >= 0 and d > D[h][w]:
			continue
		V[h][w] = True
		D[h][w] = d
		walked.append((d,h,w))
		for (x,y) in walk:
			hh,ww = h+x, w+y
			if validPosition(hh, ww) and S[hh][ww] == "." and D[hh][ww] == -1:
				search.append((d, hh, ww))
	
	next_search=[]
	for (d,h,w) in walked:
		for (x,y) in warp:
			hh,ww = h+x, w+y
			if validPosition(hh, ww) and not V[hh][ww] and S[hh][ww] == "." and D[hh][ww] == -1:
				V[hh][ww] = True
				next_search.append((d+1, hh, ww))
	if len(next_search) == 0:
		break
	search = next_search

print(D[Gh][Gw])

Solution (Python):
from collections import deque

def solve(S, N, H, W, Ch, Cw, Dh, Dw):
    d = deque()
    
    d.append((Ch, Cw))
    count = 0
    uplr = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while d:
        tmp = deque()

        while d:
            h, w = d.pop()
            N[h][w] = count
            if h == Dh and w == Dw:
                return count

            for (dh, dw) in uplr:
                if S[h+dh][w+dw] == '.' and N[h+dh][w+dw] == -1:
                    d.append((h+dh, w+dw))
            
            tmp.append((h, w))
        

        while tmp:
            h, w = tmp.pop()
            for dh in range(-2, 3):
                if dh+h < 1 or dh+h > H:
                    continue
                for dw in range(-2, 3):
                    if dw+w < 1 or dw+w > W:
                        continue
                    if S[h+dh][w+dw] == '.' and N[h+dh][w+dw] == -1:
                        d.append((h+dh, w+dw))

        
        
        

        count += 1
    return -1

def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    wall = '
    S = [wall] + ['

    N = [[-1] * (W+2) for i in range(H+2)]
    
    
    
    print(solve(S, N, H, W, Ch, Cw, Dh, Dw))

if __name__ == '__main__':
    main()

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 = [list(input()) for _ in range(h)]

d = deque()
d.append([ch-1, cw-1])
dist = [[float('inf')] * w for _ in range(h)]
dist[ch-1][cw-1] = 0
while d:
    x, y = d.popleft()
    for i in range(-2, 3):
        for j in range(-2, 3):
            if 0 <= x + i < h and 0 <= y + j < w and s[x+i][y+j] == '.':
                if i == 0 and j == 0:
                    continue
                elif (i == 1 and j == 0) or (i == 0 and j == 1) or (i == -1 and j == 0) or (i == 0 and j == -1):
                    if dist[x+i][y+j] > dist[x][y]:
                        dist[x+i][y+j] = dist[x][y]
                        d.appendleft([x+i, y+j])
                else:
                    if dist[x+i][y+j] > dist[x][y] + 1:
                        dist[x+i][y+j] = dist[x][y] + 1
                        d.append([x+i, y+j])

print(dist[dh-1][dw-1] if dist[dh-1][dw-1] != float('inf') else -1)

Solution (Python):
def main():
	inf=10**9
	h,w=map(int,input().split())
	a,b=map(int,input().split())
	c,d=map(int,input().split())
	s=[input() for _ in range(h)]
	cnt=[[inf]*w for _ in range(h)]
	LIS=((-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))
	cnt[a-1][b-1]=0
	new_stack=[(a-1,b-1)]
	for i in range(inf):
		if len(new_stack)==0:
			break
		lis=[]
		stack=new_stack.copy()
		new_stack=[]
		while stack:
			r=stack.pop()
			lis.append(r)
			x,y=r[0],r[1]
			for dx,dy in ((-1,0),(0,1),(1,0),(0,-1)):
				if 0<=x+dx<h and 0<=y+dy<w:
					if s[x+dx][y+dy]=="." and cnt[x+dx][y+dy]==inf:
						cnt[x+dx][y+dy]=i
						stack.append((x+dx,y+dy))
		for x,y in lis:
			for dx,dy in LIS:
				if 0<=x+dx<h and 0<=y+dy<w:
					if s[x+dx][y+dy]=="." and cnt[x+dx][y+dy]==inf:
						cnt[x+dx][y+dy]=i+1
						new_stack.append((x+dx,y+dy))		
	print(cnt[c-1][d-1] if cnt[c-1][d-1]!=inf else -1)
if __name__ == '__main__':
	main()

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    H,W = LI()
    ch, cw = _LI()
    dh, dw = _LI()
    m = [[0] * W for _ in range(H)]
    for i in range(H):
        s = SI()
        for j in range(W):
            if s[j] == "
                m[i][j] = -1

    z = collections.deque()
    z.append((ch,cw,1))
    while z:
        x,y,c = z.popleft()
        if m[x][y]: continue
        q = collections.deque()
        q.append((x,y))
        m[x][y] = c
        r = [(x,y)]
        while q:
            x,y = q.popleft()
            if x == dh and y == dw:
                print(c-1)
                return
            for dx,dy in ((0,1),(1,0),(-1,0),(0,-1)):
                nx = x + dx
                ny = y + dy
                if not(0<= nx < H and 0<= ny < W): continue
                if m[nx][ny]: continue
                m[nx][ny] = c
                q.append((nx,ny))
                r.append((nx,ny))
        for x,y in r:
            for dx in range(-2,3):
                nx = x + dx
                if not(0<= nx < H): continue
                for dy in range(-2,3):
                    ny = y + dy
                    if not(0<= ny < W): continue
                    if m[nx][ny]: continue
                    z.append((nx,ny,c+1))
    print(-1)
if __name__ == '__main__':
    main()

Solution (Python):






h, w = list(map(int, input().split()))

start = list(map(int, input().split()))
goal = list(map(int, input().split()))

masu = [input() for i in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

inf = 10 ** 7
distance = [[inf for _ in range(w)] for _ in range(h)]

from collections import deque

queue = deque([])
distance[start[0]-1][start[1]-1] = 0
queue.append((start[0]-1, start[1]-1, 0))

while True:
    if len(queue) == 0:
        break
    now = queue.popleft()
    now_h = now[0]
    now_w = now[1]
    now_distance = now[2]
    now_distance_matrix = distance[now_h][now_w]

    if now_distance > now_distance_matrix:
        
        continue
    distance[now_h][now_w] = now_distance

    for hh in range(now_h - 2, now_h + 2+1):
        for ww in range(now_w - 2, now_w + 2+1):
            if not (0 <= hh <= h-1 and 0 <= ww <= w-1):
                continue
            if masu[hh][ww] == '
                continue
            if distance[hh][ww] <= now_distance:
                continue
            queue.append((hh, ww, now_distance + 1))

    for i in range(4):
        next_h = now_h + dx[i]
        next_w = now_w + dy[i]
        if not (0 <= next_h <= h-1 and 0 <= next_w <= w-1):
            continue
        if masu[next_h][next_w] == '
            continue
        if distance[next_h][next_w] <= now_distance:
            continue
        else:
            distance[next_h][next_w] = now_distance
            queue.appendleft((next_h, next_w, now_distance))

t = distance[goal[0]-1][goal[1]-1]
if t == inf:
    print(-1)
else:
    print(t)

Solution (Python):
from collections import deque


def main():
    h, w = map(int, input().split())
    c = list(map(lambda x: int(x) - 1, input().split()))
    d = list(map(lambda x: int(x) - 1, input().split()))
    grid = [list(input()) for _ in range(h)]
    q = deque([c])
    max_val = 10 ** 10
    dist = [[max_val for _ in range(w)] for _ in range(h)]
    dist[c[0]][c[1]] = 0
    next_d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    while q:
        now_x, now_y = q.popleft()
        for dx, dy in next_d:
            nx = now_x + dx
            ny = now_y + dy
            if not (0 <= nx < h and 0 <= ny < w):
                continue
            elif grid[nx][ny] == "
                continue
            if dist[nx][ny] > dist[now_x][now_y]:
                dist[nx][ny] = dist[now_x][now_y]
                if [nx, ny] == d:
                    continue
                q.appendleft([nx, ny])
        for dx, dy in [[0, 2], [1, 2], [1, 1], [2, 2], [2, 0], [2, 1]]:
            for cx, cy in [[1, 1], [1, -1], [-1, -1], [-1, 1]]:
                nx = now_x + dx * cx
                ny = now_y + dy * cy
                if not (0 <= nx < h and 0 <= ny < w):
                    continue
                elif grid[nx][ny] == "
                    continue
                if dist[nx][ny] > dist[now_x][now_y] + 1:
                    dist[nx][ny] = dist[now_x][now_y] + 1
                    if [nx, ny] == d:
                        continue
                    q.append([nx, ny])
    print(dist[d[0]][d[1]] if dist[d[0]][d[1]] != max_val else -1)


if __name__ == '__main__':
    main()

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

maze=[list(input()) for _ in range(h)]

from collections import deque
stack = deque([(sy,sx)])
maze[sy][sx]=0

checked=[[0]*w for _ in range(h)]


while len(stack)>0:
    (y,x)=stack.popleft()
    if checked[y][x]==0:
        checked[y][x]=1
        if (y,x)==(gy,gx):
            print(maze[y][x])
            exit()
        for (my,mx) in ((1,0),(0,1),(-1,0),(0,-1)):
            ny=my+y
            nx=mx+x
            if 0<=ny<h and 0<=nx<w:
                if maze[ny][nx]=="." or (maze[ny][nx]!="
                    stack.appendleft((ny,nx))
                    maze[ny][nx]=maze[y][x]
                
                elif maze[ny][nx]=="
                    ny+=my
                    nx+=mx
                    if 0<=ny<h and 0<=nx<w:
                        if maze[ny][nx]=="." or (maze[ny][nx]!="
                            stack.append((ny,nx))
                            maze[ny][nx]=maze[y][x]+1
        
        for (my,mx) in ((1,1),(-1,-1),(-1,1),(1,-1)):
            for k in (1,2):
                ny=my*k+y
                nx=mx*k+x
                if 0<=ny<h and 0<=nx<w:
                    if maze[ny][nx]=="." or (maze[ny][nx]!="
                        stack.append((ny,nx))
                        maze[ny][nx]=maze[y][x]+1
        for (my,mx) in ((1,2),(-1,-2),(-1,2),(1,-2),(2,1),(-2,-1),(-2,1),(2,-1)):
            ny=my+y
            nx=mx+x
            if 0<=ny<h and 0<=nx<w:
                if maze[ny][nx]=="." or (maze[ny][nx]!="
                    stack.append((ny,nx))
                    maze[ny][nx]=maze[y][x]+1


    
print(-1)

Solution (Python):
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    H, W = read_ints()
    Ch, Cw = read_ints()
    Ch -= 1
    Cw -= 1
    Dh, Dw = read_ints()
    Dh -= 1
    Dw -= 1
    table = []
    for _ in range(H):
        table.append(list(input()))
    costs = [
        [math.inf for _ in range(W)] for _ in range(H)
    ]

    def dfs(points, cost):
        Q = list(points)
        discovered = list(points)
        while Q:
            i, j = Q.pop()
            for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                if 0 <= x < H and 0 <= y < W and table[x][y] == '.' and costs[x][y] == math.inf:
                    costs[x][y] = cost
                    Q.append((x, y))
                    discovered.append((x, y))
        reachables = []
        for x, y in discovered:
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    new_x, new_y = x+dx, y+dy
                    if 0 <= new_x < H and 0 <= new_y < W and table[new_x][new_y] == '.' and costs[new_x][new_y] == math.inf:
                        costs[new_x][new_y] = cost+1
                        reachables.append((new_x, new_y))
        return reachables

    cost = 0
    Q = [(Ch, Cw)]
    costs[Ch][Cw] = 0
    while Q:
        Q = dfs(Q, cost)
        cost += 1
    if costs[Dh][Dw] == math.inf:
        return -1
    return costs[Dh][Dw]


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

Solution (Python):
import collections, itertools
H, W, ch, cw, dh, dw, *S = open(0).read().split()
H, W, ch, cw, dh, dw = [int(_) + 1 for _ in [H, W, ch, cw, dh, dw]]
H += 3
W += 3
S = ['
                             for s in S] + ['
Dist = [[None] * W for _ in range(H)]
Q = collections.deque([(0, ch, cw)])
while Q:
    d, ox, oy = Q.popleft()
    if Dist[ox][oy] is not None:
        continue
    stack = [[ox, oy]]
    warp = set()
    while stack:
        x, y = stack.pop()
        if (x, y) == (dh, dw):
            print(d)
            exit()
        Dist[x][y] = d
        for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            nx, ny = x + dx, y + dy
            if Dist[nx][ny] is None:
                if S[nx][ny] == '.':
                    stack += [[nx, ny]]
                else:
                    warp.add((x, y))
    for x, y in warp:
        for dx, dy in itertools.product(range(-2, 3), repeat=2):
            nx, ny = x + dx, y + dy
            if Dist[nx][ny] is None and S[nx][ny] == '.':
                Q += [(d + 1, nx, ny)]
print(-1)

Solution (Python):

import sys
sys.setrecursionlimit(2_000_000)

def solve(H, W, CH, DH, CW, DW, S):
    from collections import deque
    costs = [[float("inf")] * W for _ in range(H)]
    
    def bfs():
        q = deque([(CH-1, CW-1, 0)])
        while q:
            h, w, c = q.popleft()
            if h == (DH-1) and w == (DW-1):
                return c
            if costs[h][w] < c:
                continue
            costs[h][w] = c
            for dh, dw in zip((0, 0, 1, -1), (1, -1, 0, 0)):
                nh, nw = h + dh, w + dw
                if not (0 <= nh < H and 0 <= nw < W):
                    continue
                if S[nh][nw] == "
                    continue
                if costs[nh][nw] <= c:
                    continue
                costs[nh][nw] = c
                q.appendleft((nh, nw, c))
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    nh, nw = h + dh, w + dw
                    if not (0 <= nh < H and 0 <= nw < W):
                        continue
                    if S[nh][nw] == "
                        continue
                    if costs[nh][nw] <= (c + 1):
                        continue
                    costs[nh][nw] = c+1
                    q.append((nh, nw, c+1))
        return -1
    
    return bfs()

    

def main():
    H, W = map(int, input().split())
    CH, CW = map(int, input().split())
    DH, DW = map(int, input().split())
    S = [input() for _ in range(H)]
    print(solve(H, W, CH, DH, CW, DW, S))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):
from collections import deque

r, c = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
maze = [list(input()) for i in range(r)]

sy -= 1
sx -= 1
gy -= 1
gx -= 1




def find_shortest():
    
    d = [[float("inf")] * c for i in range(r)]
    
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    ddx = [-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
    ddy = [2,1,0,-1,-2,2,1,-1,-2,2,-2,2,1,-1,-2,2,1,0,-1,-2]

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


    while que or queq:

        
        while que:
            
            p = que.popleft()
            queq.append(p)
            
            if p[0] == gy and p[1] == gx:
                key = 1
                break
            
            for i in range(4):
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]

                
                
                if 0 <= nx < r and 0 <= ny < c and maze[nx][ny] != "
                    
                    que.append((nx, ny))
                    
                    d[nx][ny] = d[p[0]][p[1]]
        while queq:
            p = queq.popleft()
            
            for i in range(20):
                nx = p[0] + ddx[i]
                ny = p[1] + ddy[i]

                
                
                if 0 <= nx < r and 0 <= ny < c and maze[nx][ny] != "
                    
                    que.append((nx, ny))
                    
                    d[nx][ny] = d[p[0]][p[1]]+1
    if d[gy][gx] != float('inf'):
        return d[gy][gx]
    else:
        return -1

ans = find_shortest()
print(ans)