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 sys
from collections import deque, defaultdict

sys.setrecursionlimit(10000)

H, W = map(int, input().split())
C = tuple(map(int, input().split()))
D = tuple(map(int, input().split()))
S = [list(input()) for _ in range(H)]

d = [(0, 1), (1, 0), (0, -1), (-1, 0)]


def dfs(h, w, i):
    S[h][w] = i

    for dh, dw in d:
        nh = h + dh
        nw = w + dw
        if nh < 0 or nh >= H or nw < 0 or nw >= W:
            continue
        if S[nh][nw] != '.':
            continue
        dfs(nh, nw, i)



count = 1
for h in range(H):
    for w in range(W):
        if S[h][w] != '.':
            continue
        dfs(h, w, count)
        count += 1


graph = defaultdict(set)
for h in range(H):
    for w in range(W):
        if S[h][w] == '
            continue

        for dh in range(-2, 3):
            for dw in range(-2, 3):
                nh = h + dh
                nw = w + dw
                if nh < 0 or nh >= H or nw < 0 or nw >= W:
                    continue
                if S[nh][nw] == '
                    continue
                graph[S[h][w]].add(S[nh][nw])

start = S[C[0]-1][C[1]-1]
goal = S[D[0]-1][D[1]-1]


def shortest_dist(graph, start, goal):
    queue = deque([start])
    visited = set()
    visited.add(start)
    dist = defaultdict(int)
    dist[start] = 0
    while queue:
        current_vertex = queue.popleft()
        if current_vertex == goal:
            return dist[goal]
        for v in graph[current_vertex]:
            if v not in visited:
                visited.add(v)
                queue.append(v)
                dist[v] = dist[current_vertex] + 1
    return -1


ans = shortest_dist(graph, start, goal)

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6
mod = 10 ** 9 + 7 

from decimal import *




def main():
	H, W = MAP()
	Ch, Cw = MAP()
	Dh, Dw = MAP()
	S = [input() for _ in range(H)]

	cnt = [[INF]*W for _ in range(H)]
	cnt[Ch-1][Cw-1] = 0

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

	q = deque([(Ch-1, Cw-1, 0)])
	while q:
		y, x, c = q.popleft()
		if cnt[y][x] != c:
			continue
		flg = True
		for i in range(24):
			if i == 4 and flg:
				break
			ny = y + dy[i]
			nx = x + dx[i]
			if ny < 0 or nx < 0 or H <= ny or W <= nx:
				continue
			elif i < 4:
				if S[ny][nx] == "." and c < cnt[ny][nx]:
					cnt[ny][nx] = c
					q.appendleft((ny, nx, c))
				elif S[ny][nx] == "
					flg = False
			elif 4 <= i and S[ny][nx] == "." and c+1 < cnt[ny][nx]:
				cnt[ny][nx] = c+1
				q.append((ny, nx, c+1))


	if cnt[Dh-1][Dw-1] == INF:
		print(-1)
	else:
		print(cnt[Dh-1][Dw-1])

if __name__ == '__main__':
	main()

Solution (Python):
from collections import deque
H, W = map(int, input().split())
cy, cx = map(int, input().split())
dy, dx = map(int, input().split())
cy -= 1
cx -= 1
dy -= 1
dx -= 1
d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
S = [input() for _ in range(H)]

worps = [[float('inf')]*W for _ in range(H)]
q = deque([[cy, cx]])

worps[cy][cx] = 0
while q:
    y, x = q.popleft()
    worp = worps[y][x]

    for h, w in d:
        ny, nx = y+h, x+w
        if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == "." and worp < worps[ny][nx]:
            worps[ny][nx] = worp
            q.appendleft([ny, nx])

    worp += 1
    for h in range(-2+y, 3+y):
        for w in range(-2+x, 3+x):
            if 0 <= h < H and 0 <= w < W and S[h][w] == "." and worp < worps[h][w]:
                worps[h][w] = worp
                q.append([h, w])

ans = worps[dy][dx]
if ans != float('inf'):
    print(ans)
else:
    print(-1)

Solution (Python):
from collections import deque


def main():

    def f(hi, wi):
        return hi * w + wi

    h, w = map(int, input().split())
    sh, sw = map(int, input().split())
    gh, gw = map(int, input().split())

    s = [input() for _ in range(h)]
    INF = 10 ** 9

    sh -= 1
    sw -= 1
    gh -= 1
    gw -= 1

    dq = deque([f(sh, sw)])
    dist = [[INF] * w for _ in range(h)]
    dist[sh][sw] = 0

    while dq:
        i = dq.popleft()
        hi, wi = divmod(i, w)

        for dh in range(-2, 3):
            for dw in range(-2, 3):
                if dh == 0 and dw == 0:
                    continue
                nh = hi + dh
                nw = wi + dw
                if 0 <= nh <= h - 1 and 0 <= nw <= w - 1 and s[nh][nw] == ".":
                    if abs(dh) + abs(dw) == 1:
                        if dist[hi][wi] < dist[nh][nw]:
                            dist[nh][nw] = dist[hi][wi]
                            dq.appendleft(f(nh, nw))
                    else:
                        if dist[hi][wi] + 1 < dist[nh][nw]:
                            dist[nh][nw] = dist[hi][wi] + 1
                            dq.append(f(nh, nw))

    ans = dist[gh][gw]
    if ans == INF:
        ans = -1

    print(ans)


if __name__ == "__main__":
    main()

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):
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    sh, sw = map(int, input().split())
    sh -= 1
    sw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1

    S = [input().strip("\n") for _ in range(H)]

    q = deque()
    P = [[-1 for _ in range(W)] for h in range(H)]
    q.append((0, sh, sw))
    while q:
        d, h, w = q.popleft()
        if P[h][w] == -1:
            P[h][w] = d
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if 0<=h+dh<H and 0<=w+dw<W and S[h+dh][w+dw] == "." and P[h+dh][w+dw] == -1:
                        if abs(dh) + abs(dw) == 1:
                            q.appendleft((d, h+dh, w+dw))
                        else:
                            q.append((d+1, h+dh, w+dw))
    print(P[fh][fw])
    

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import heapq
import math
from collections import deque

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

tobool = lambda s: s == "

S = [
  list(map(tobool, input())) for _ in range(H)
]
visited_m = [[False for w in range(W) ] for h in range(H)]
cost_m = [[math.inf for w in range(W) ] for h in range(H)]

def enum_moveA(Ch, Cw):
  return [(Ch-1, Cw), (Ch+1, Cw), (Ch, Cw-1), (Ch, Cw+1)]

def enum_moveB(Ch, Cw):
  return [
    (Ch-2, Cw-2), (Ch-2, Cw-1), (Ch-2, Cw), (Ch-2, Cw+1), (Ch-2, Cw+2),
    (Ch-1, Cw-2), (Ch-1, Cw-1), (Ch-1, Cw+1), (Ch-1, Cw+2),
    (Ch, Cw-2), (Ch, Cw+2),
    (Ch+1, Cw-2), (Ch+1, Cw-1), (Ch+1, Cw+1), (Ch+1, Cw+2),
    (Ch+2, Cw-2), (Ch+2, Cw-1), (Ch+2, Cw), (Ch+2, Cw+1), (Ch+2, Cw+2),
  ]

d = deque()
d.appendleft((0, Ch, Cw))
while True:
  if len(d) == 0:
    break
  visited_m[Ch][Cw] = True
  c_cost, Ch, Cw = d.popleft()
  if Ch == Dh and Cw == Dw:
    break
  for h, w in enum_moveA(Ch, Cw):
    if 0 <= h <H and 0 <= w <W:
      tmp_cost = cost_m[h][w]
      visited = visited_m[h][w]
      kabe = S[h][w]
      if c_cost + 0 < tmp_cost and not visited and not kabe:
        cost_m[h][w] = c_cost + 0
        d.appendleft((c_cost + 0, h, w))
        
  for h, w in enum_moveB(Ch, Cw):
    if 0 <= h <H and 0 <= w <W:
      tmp_cost = cost_m[h][w]
      visited = visited_m[h][w]
      kabe = S[h][w]
      if c_cost + 1 < tmp_cost and not visited and not kabe:
        cost_m[h][w] = c_cost + 1
        d.append((c_cost + 1, h, w))
    
total_cost = cost_m[Dh][Dw]
if total_cost < math.inf:
  print(total_cost)
else:
  print(-1)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "

from collections import defaultdict, deque

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0

q = deque([(0, start)]) 


dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = q.popleft()
    ux,uy = divmod(pu,w)
    
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):


        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="
            continue

        if seen[u] is None or seen[u]>num:
            seen[u] = num
            if vv==0:
                q.appendleft((num, u))
            else:
                q.append((num,u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)

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

def main():
    H, W = mapint()
    ch, cw = mapint()
    dh, dw = mapint()
    maze = [list(input()) for _ in range(H)]
    
    dirc = ((-1, 0), (1, 0), (0, -1), (0, 1))
    magic = ((-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))
    from collections import deque
    Q = deque([(ch-1, cw-1)])
    
    dist = [[10**18]*W for _ in range(H)]
    dist[ch-1][cw-1] = 0
    while Q:
        y, x = Q.popleft()
        for dy, dx in dirc:
            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 dist[ny][nx]>dist[y][x]:
                dist[ny][nx] = dist[y][x]
                Q.appendleft((ny, nx))
        
        for dy, dx in magic:
            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 dist[ny][nx]>dist[y][x]+1:
                dist[ny][nx] = dist[y][x]+1
                Q.append((ny, nx))
    if dist[dh-1][dw-1]>=10**17:
        print(-1)
    else:
        print(dist[dh-1][dw-1])
main()

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w = LI()
ch, cw = LI()
dh, dw = LI()
s = [input() for _ in range(h)]

dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
que = deque([(cw-1, ch-1)])
d = [[10**10] * w for _ in range(h)]
d[ch-1][cw-1] = 0
while que:
    x, y = que.popleft()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if s[ny][nx] == '.' and d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.appendleft((nx, ny))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx, ny = x + i, y + j
            if 0 <= nx < w and 0 <= ny < h:
                if s[ny][nx] == '.' and d[ny][nx] > d[y][x] + 1:
                    d[ny][nx] = d[y][x] + 1
                    que.append((nx, ny))
if d[dh-1][dw-1] == 10**10:
    print(-1)
else:
    print(d[dh-1][dw-1])

Solution (Python):
from collections import deque
import sys

sys.setrecursionlimit(10**7)
H,W=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

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

maze=[[i for i in input()] for _ in range(H)]

visited = [[-1]*W for _ in range(H)]
queue = deque([])
queue.append((sx,sy))
visited[sy][sx] = 0
def bfs(v,queue,gx,gy,maze):
    check=deque([])



    while len(queue) != 0:
        n = queue.popleft()
        x,y = n[0], n[1]
        flag=0

        if n == (gx,gy):
            print(v)
            exit()

        for i, j in [(1,0), (0,1), (-1,0), (0,-1)]:
            if (x+i < 0) or (x+i >=W) or (y+j < 0) or (y+j >=H):
                continue
            if maze[y+j][x+i] == '.' and visited[y+j][x+i] == -1:
                queue.append((x+i,y+j))
                visited[y+j][x+i] = v
            elif maze[y+j][x+i] == '
                flag=1
        if flag==1:
            check.append((x,y))

    while len(check) != 0:
        n=check.popleft()
        x,y=n[0],n[1]
        for i in range(-2,3):
            for j in range(-2,3):
                if (x+i < 0) or (x+i >=W) or (y+j < 0) or (y+j >=H):
                    continue
                if maze[y+j][x+i] == '.' and visited[y+j][x+i] == -1:
                    queue.append((x+i,y+j))
                    visited[y+j][x+i] = v+1

    if len(queue)!=0:
        bfs(v+1,queue,gx,gy,maze)



bfs(0,queue,gx,gy,maze)
print(-1)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from queue import deque 
q = deque([(0, start)]) 


dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = q.popleft()
    ux,uy = divmod(pu,w)
    
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):


        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="
            continue

        if seen[u] is None or seen[u]>num:
            seen[u] = num
            if vv==0:
                q.appendleft((num, u))
            else:
                q.append((num,u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
map = []
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visit = [[-1]*w for i in range(h)]
visit[sy - 1][sx - 1] = 0
warp = []
cnt = 0

for i in range(-2, 3):
    for j in range(-2, 3):
        if i == 0 and j == 0:
            continue
        else:
            warp.append([i, j])

for i in range(h):
    s = input()
    map.append(s)

route = deque([[sy - 1, sx - 1]])
wroute = deque()

while route:
    while route:
        y, x = route.popleft()
        wroute.append([y, x])
        for i, j in move:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] == visit[y][x]:
                        continue
                    visit[k][l] = visit[y][x]
                    route.append([k, l])
    while wroute:
        y, x = wroute.popleft()
        for i, j in warp:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] != -1:
                        continue
                    visit[k][l] = visit[y][x] + 1
                    route.append([k, l])
    cnt += 1

print(visit[gy - 1][gx - 1])

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
import heapq


def read():
    H, W = map(int, input().strip().split())
    CH, CW = map(int, input().strip().split())
    DH, DW = map(int, input().strip().split())
    S = [[0 for j in range(W)] for i in range(H)]
    for i in range(H):
        s = list(input().strip())
        for j in range(W):
            if s[j] == "
                S[i][j] = -2
            else:
                S[i][j] = -1
    return H, W, CH, CW, DH, DW, S


def solve(H, W, CH, CW, DH, DW, S, INF=10**7):
    DIR = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    id = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == -1:
                id += 1
                S[i][j] = id
                q = deque()
                q.append((i, j))
                while q:
                    y, x = q.popleft()
                    for dy, dx in DIR:
                        ny, nx = y+dy, x+dx
                        if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == -1:
                            S[ny][nx] = id
                            q.append((ny, nx))

    start_id = S[CH-1][CW-1]
    goal_id = S[DH-1][DW-1]
    if start_id == goal_id:
        return 0

    
    N = id
    G = [dict() for i in range(N)]

    
    for i in range(H):
        for j in range(W):
            source_id = S[i][j]
            if source_id > 0:
                for k in range(i-2, i+3):
                    for l in range(j-2, j+3):
                        if 0 <= k < H and 0 <= l < W:
                            target_id = S[k][l]
                            if target_id > 0 and source_id != target_id:
                                G[source_id-1][target_id-1] = 1
                                G[target_id-1][source_id-1] = 1
    
    visited = [-1 for i in range(N)]
    q = deque()
    visited[start_id-1] = 0
    q.append(start_id-1)
    while q:
        u = q.popleft()
        if u == goal_id-1:
            break
        for v in G[u].keys():
            if visited[v] == -1:
                visited[v] = visited[u] + 1
                q.append(v)
    return visited[goal_id-1]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Solution (Python):
from collections import deque

diffs = [(-1, 0), (0, -1), (0, 1), (1, 0)]

h, w = map(int, input().split())
start_point = tuple(map(lambda x: int(x) - 1, input().split()))
goal_point = tuple(map(lambda x: int(x) - 1, input().split()))
maze = [input() for _ in range(h)]

counts = [[-1] * w for _ in range(h)]

counts[start_point[0]][start_point[1]] = 0
point_queue = deque([start_point])

while point_queue:
    connected_queue = deque()
    while point_queue:
        curr_h, curr_w = point_queue.pop()
        connected_queue.append((curr_h, curr_w))

        for diff_h, diff_w in diffs:
            next_h = curr_h + diff_h
            next_w = curr_w + diff_w

            if not (0 <= next_h < h and 0 <= next_w < w):
                continue

            if maze[next_h][next_w] == '
                continue

            if (next_h, next_w) == goal_point:
                print(counts[curr_h][curr_w])
                exit(0)

            if counts[next_h][next_w] != -1:
                continue

            counts[next_h][next_w] = counts[curr_h][curr_w]
            point_queue.append((next_h, next_w))
            connected_queue.append((next_h, next_w))

    while connected_queue:
        curr_h, curr_w = connected_queue.pop()
        for diff_h in range(-2, 3):
            for diff_w in range(-2, 3):
                next_h = curr_h + diff_h
                next_w = curr_w + diff_w

                if not (0 <= next_h < h and 0 <= next_w < w):
                    continue

                if maze[next_h][next_w] == '
                    continue

                if (next_h, next_w) == goal_point:
                    print(counts[curr_h][curr_w] + 1)
                    exit(0)

                if counts[next_h][next_w] != -1:
                    continue

                counts[next_h][next_w] = counts[curr_h][curr_w] + 1
                point_queue.append((next_h, next_w))

print(-1)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
field = [["
        [["
        [list("
        [["
        [["
sy += 1
sx += 1
gy += 1
gx += 1          
          
dxy1 = [(0,1), (0,-1), (1,0), (-1,0)]
dxy2 = [(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)]


goal = False
INF = 10**9
cnt = [[INF]*(w+4) for i in range(h+4)]

q = deque()
q.append([sy, sx])
cnt[sy][sx] = 0

while goal == False and q:
    y, x = q.pop()
    now = cnt[y][x]
    flg = False
    for dy, dx in dxy1:
        ny, nx = y + dy, x + dx
        if ny == gy and nx == gx:
            cnt[ny][nx] = now
            goal = True
            flg = True
            break
        if field[ny][nx] == '
            continue
        if field[ny][nx] == '.' and cnt[ny][nx] > now:
            q.append([ny, nx])
            cnt[ny][nx] = now
            flg = True
    if goal:
        break
    for dy, dx in dxy2:
        ny, nx = y + dy, x + dx
        if field[ny][nx] == '
            continue
        if field[ny][nx] == '.' and cnt[ny][nx] > now + 1:
            q.appendleft([ny, nx])
            cnt[ny][nx] = now + 1
print(cnt[gy][gx]) if cnt[gy][gx] < INF else print(-1)

Solution (Python):
from math import trunc
import sys
import copy
from collections import deque
import collections
import itertools
stdin = sys.stdin
import math

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  


h, w = na()
sh, sw = na()
gh, gw = na()

map = []
for _ in range(h):
    s = ns()
    map.append([0 if i=="." else 1 for i in s])

visited = [[1000000 for j in range(w)] for i in range(h)]

def warp(nh, nw, now_warp):
    next_p = []
    topleft = [nh-2, nw-2]
    for i in range(5):
        for j in range(5):
            neh = topleft[0]+i
            new = topleft[1]+j
            if check_position(neh, new, now_warp+1):
                next_p.append([neh, new])
    return next_p


def check_position(hi, wi, now_warp):
    if hi<0 or hi>=h or wi<0 or wi>=w or map[hi][wi]==1 or visited[hi][wi] <= now_warp:
        return False
    return True


positions = deque()
positions.append([sh-1, sw-1, 0])
while len(positions)>0:
    warp_positions = deque()
    while len(positions)>0:
        nh, nw, now_warp = positions.popleft()

        if now_warp >= visited[nh][nw]:
            continue

        visited[nh][nw] = now_warp
        move_cnt = 0
        if check_position(nh+1, nw, now_warp):
            positions.append([nh+1, nw, now_warp])
            move_cnt += 1
        
        if check_position(nh, nw+1, now_warp):
            positions.append([nh, nw+1, now_warp])
            move_cnt += 1
        
        if check_position(nh-1, nw, now_warp):
            positions.append([nh-1, nw, now_warp])
            move_cnt += 1
        
        if check_position(nh, nw-1, now_warp):
            positions.append([nh, nw-1, now_warp])
            move_cnt += 1

        if move_cnt<4:
            warp_positions.append([nh, nw, now_warp])
    
    while len(warp_positions)>0:
        nh, nw, now_warp = warp_positions.popleft()
        next_warps = warp(nh, nw, now_warp)
        for p in next_warps:
            positions.append([p[0], p[1], now_warp+1])

print(-1 if visited[gh-1][gw-1]==1000000 else visited[gh-1][gw-1])

Solution (Python):

from collections import deque
import sys
def main(H, W, C, D, S):
    INF = 10**6
    dist = [[INF] * W for _ in range(H)]
    di, dj = D
    dist[di][dj] = 0
    q = deque([(di, dj, 0)])
    while q:
        i, j, d = q.popleft()
        if d > dist[i][j]: continue
        for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                if dist[ni][nj] > d:
                    dist[ni][nj] = d
                    q.appendleft((ni, nj, d))
        for ni in range(i - 2, i + 2 + 1, 1):
            if not(0 <= ni < H): continue
            dni = dist[ni]
            sni = S[ni]
            for nj in range(j - 2, j + 2 + 1, 1):
                if 0 <= nj < W and sni[nj] == '.':
                    if dni[nj] > d + 1:
                        dni[nj] = d + 1
                        q.append((ni, nj, d + 1))

    ans = dist[C[0]][C[1]]
    print(ans if ans < INF else -1)


if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = tuple(map(lambda x: int(x) - 1, input().split()))
    D = tuple(map(lambda x: int(x) - 1, input().split()))
    S = [list(input().rstrip()) for _ in range(H)]
    main(H, W, C, D, S)

Solution (Python):
from collections import deque

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


widou = []

for i in range(-2,3):
    for j in range(-2, 3):
        widou.append((i, j))
widou.remove((0,0))
widou.remove((1,0))
widou.remove((0,1))
widou.remove((-1,0))
widou.remove((0,-1))


start = (ch-1, cw-1)
goal = (dh-1, dw-1)

explored = set()
tempexplored = set()

yexp= deque()
yexp.append(start)
ytemp= deque()
ytemp.append(start)

wap = 0


while yexp:
    now = yexp.popleft()
    ytemp.popleft()

    if now == goal:
        print(wap)
        exit(0)

    x = now[0]
    y = now[1]

    explored.add((x, y))
    tempexplored.add((x, y))

    idou = [(1,0), (0,1), (0,-1), (-1,0)]
    for i, j in idou:
        a = x + i
        b = y + j
        if 0 <= a < h and 0 <= b < w:
            if ls[a][b] == '.':
                if (a, b) not in explored:
                    
                    yexp.append((a,b))
                    ytemp.append((a,b))
                    explored.add((a,b))
                    tempexplored.add((a,b))
    
    
    


    if len(ytemp) ==0:
        
        wap += 1
        for s,t in tempexplored:
            
            for i, j in widou:
                
                a = s + i
                b = t + j
                


                if 0 <= a < h and 0 <= b < w:
                    
                    if ls[a][b] == '.':
                        if (a, b) not in explored:
                            
                            yexp.append((a, b))
                            ytemp.append((a, b))
                            explored.add((a, b))
        tempexplored = set()
        
        
        
print('-1')