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())

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

S = [list(map(str,input())) for _ in range(H)]


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

pathB =[]
for n in range(5):
    for m in range(5):
        pathB.append((n-2,m-2))

visited  =[[-1]*W for _ in range(H)]

queue =deque([])
queue.append((ch-1,cw-1,0))
while queue:
    h,w,d =queue.popleft()
    if visited[h][w] ==-1:
        visited[h][w] =d
        
        for h1,w1 in pathA:
            newh = h1+h
            neww = w1+w
            if newh>=0 and newh<H and neww >=0 and neww <W and S[newh][neww]==".":
                queue.appendleft((newh,neww,d))
        
        for h1,w1 in pathB:
            newh = h1+h
            neww = w1+w
            if newh>=0 and newh<H and neww >=0 and neww <W and S[newh][neww]==".":
                queue.append((newh,neww,d+1))
                
    
print(visited[dh-1][dw-1])

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        ・復元なし
        """

        


        class Edge():
            

            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost

        def __init__(self, V):
            
            self.inf=10**20
            self.G = [[] for _ in range(V)] 
            self. _E = 0 
            self._V = V 

        
        def E(self):
            return self._E

        
        def V(self):
            return self._V

        def add(self, _from, _to, _cost):
            
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1

        def add2(self, _from, _to, _cost):
            
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2

        def shortest_path(self,s):
            
            que = [] 
            d = [self.inf] * self.V()

            
            

            d[s] = 0
            heapq.heappush(que,(0,s)) 

            while len(que)!=0:
                
                cost,v = heapq.heappop(que)

                
                if d[v] < cost:
                    continue

                
                for i in range(len(self.G[v])):
                    e = self.G[v][i] 
                    if d[e.to] > d[v] + e.cost:
                        d[e.to] = d[v] + e.cost 

                        
                        

                        heapq.heappush(que,(d[e.to],e.to)) 

            """
            path = []
            pos = g 
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                
                pos = prev[pos]
            path.reverse()
            

            return d
    
    
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        重いかも！　　members(x):要素xが属するグループに属する要素をリストで返す
        roots():全ての根の要素を返す
        group_count():グループの数を返す
        重いかも！　all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        def find(self, x):
            
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.parents[x] > self.parents[y]:
                x, y = y, x

            self.parents[x] += self.parents[y]
            self.parents[y] = x

        def size(self, x):
            return -self.parents[self.find(x)]

        def same(self, x, y):
            return self.find(x) == self.find(y)

        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    


    mod=10**9+7
    H,W=MI()
    ch,cw=MI()
    dh,dw=MI()
    ch+=1
    cw+=1
    dh+=1
    dw+=1
    
    S=[]
    S.append(["
    S.append(["
    for i in range(H):
        s=["
        S.append(s)
    S.append(["
    S.append(["
    
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    dx2=[-2,-2,-2,-2,-2,  -1,-1,-1,-1,   0,0,   1, 1,1,1,   2, 2,2,2,2]
    dy2=[-2,-1, 0, 1, 2,  -2,-1, 1, 2,  -2,2,  -2,-1,1,2,  -2,-1,0,1,2]
    
    uf=UnionFind((W+4)*(H+4))
    
    for i in range(H+2):
        for j in range(W+2):
            if S[i][j]==".":
                for k in range(4):
                    ii=i+dx[k]
                    jj=j+dy[k]
                    if S[ii][jj]==".":
                        fro=i*(W+4)+j
                        to=ii*(W+4)+jj
                        uf.union(fro,to)
    
    roots=[[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if S[i][j]==".":
                now=i*(W+4)+j
                root=uf.find(now)
                roots[i][j]=root
                
    roots_uf=uf.roots()
    from collections import defaultdict
    dd = defaultdict(int)
    
    cur=0
    for v in roots_uf:
        dd[v]=cur
        cur+=1
    
    djk=Dijkstra(len(roots_uf))
                
                
    for i in range(2,H+2):
        for j in range(2,W+2):
            if S[i][j]==".":
                for k in range(20):
                    ii=i+dx2[k]
                    jj=j+dy2[k]
                    if S[ii][jj]==".":
                        fro=roots[i][j]
                        to=roots[ii][jj]
                        if fro!=to:
                            djk.add(dd[fro],dd[to],1)
                            
    
    s=dd[roots[ch][cw]]
    g=dd[roots[dh][dw]]
    D=djk.shortest_path(s)
    ans=D[g]
    if ans>=10**6+5:
        ans=-1
    print(ans)                
    
    
                

main()

Solution (Python):
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def toi(h,w):
	return h*10000 + w
	
def fromi(v):
	return v//10000, v%10000

def main():
	
	h, w = tin()
	
	ch, cw = tin()
	start_h,start_w = ch-1,cw-1
	dh,dw = tin()
	goal_h, goal_w=dh-1, dw-1
	ll=[input() for _ in range(h)]
	pll=[[-1]*w for _ in range(h)]
	egg = [[] for _ in range(w*h)]
	
	mark=-1
	for hi in range(h):
		for wi in range(w):
			if ll[hi][wi]=='
				continue
			if pll[hi][wi] >= 0:
				continue
			mark+=1
			qq=collections.deque()
			qq.append(toi(hi,wi))
			open_list=set()
			open_list.add(toi(hi,wi))
			while len(qq)>0:
				nv = qq.popleft()
				nh, nw = fromi(nv)
				pll[nh][nw] = mark
				for dh,dw in [[1,0], [-1,0], [0,1], [0,-1]]:
					if nh + dh < 0 or nh + dh >= h:
						continue
					if nw + dw < 0 or nw + dw >= w:
						continue
					if toi(nh+dh,nw+dw) in open_list:
						continue
					if ll[nh + dh][nw+dw]=='
						egg[mark].append([nh,nw,dh,dw])
						continue
					if pll[nh + dh][nw+dw] > 0:
						continue
					qq.append(toi(nh + dh, nw+dw))
					open_list.add(toi(nh+dh,nw+dw))
					
	
	if pll[start_h][start_w] == pll[goal_h][goal_w]:
		return 0
	
	
	
	qqq=collections.deque()
	qqq.append((pll[start_h][start_w],0))
	g_pos=pll[goal_h][goal_w]
	open_list=set()
	open_list.add(-1)
	
	while len(qqq)>0:
		pos, cost = qqq.popleft()
		if pos == g_pos:
			return cost
		for [nh,nw,_h,_w] in egg[pos]:
			for dh in [-2,-1,0,1,2]:
				for dw in [-2,-1,0,1,2]:
					nnh = nh + dh
					nnw = nw + dw
					if nnh < 0 or nnh >= h:
						continue
					if nnw < 0 or nnw >= w:
						continue
					vv = pll[nnh][nnw]
					if vv in open_list:
						continue
					qqq.append((vv, cost+1))
					open_list.add(vv)
					
		
	return -1
		
		
			
		
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

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

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

s=[]
for i in range(h):
    sub=input().rstrip()
    s.append(sub)

check=[[-1]*w for i in range(h)]
stack=[(ch-1,cw-1)]
check[ch-1][cw-1]=0
d=[(1,0),(-1,0),(0,1),(0,-1)]


count=0

while True:
    temp=[]
    while len(stack)>0:
        now=stack.pop()
        temp.append(now)
        for i in d:
            x=now[0]+i[0]
            y=now[1]+i[1]
            if 0<=x<=h-1 and 0<=y<=w-1:
                if s[x][y]=='.':
                    if check[x][y]==-1:
                        check[x][y]=count
                        stack.append((x,y))

    count+=1
    for k in temp:
        for i in range(-2,3):
            for j in range(-2,3):
                x=k[0]+i
                y=k[1]+j
                if 0 <= x <= h - 1 and 0 <= y <= w - 1:
                    if s[x][y] == '.':
                        if check[x][y] == -1:
                            check[x][y]=count
                            stack.append((x,y))
    if len(stack)==0:
        break

print(check[dh-1][dw-1])

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 = {}
for i in range(1, count):
    graph[i] = 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 bfs(start, goal):
    queue = deque([start])
    visited = set()
    visited.add(start)
    dist = defaultdict(int)
    dist[start] = 0
    while queue:
        current_vertex = queue.popleft()
        for v in graph[current_vertex]:
            if v not in visited:
                visited.add(v)
                queue.append(v)
                dist[v] = dist[current_vertex] + 1
    return dist[goal] if goal in dist else -1

ans = bfs(start, goal)

print(ans)

Solution (Python):
import heapq
import sys


def input(): return sys.stdin.readline().rstrip()


H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
data = [[0]*W for i in range(H)]

for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == ".":
            data[i][j] = 1
        else:
            data[i][j] = 0


def trans(h, w):
    return W*(h) + w


P = [(0, -1), (0, 1), (1, 0), (-1, 0)]
DXY = []
for i in range(0, 3):
    for j in range(-2, 3):
        if i==0 and j==0:
            pass
        else:
            DXY.append((i,j))
            
G = [[] for i in range(H*W)]
H_L = [i for i in range(H)]
W_L = [i for i in range(W)]
for i in H_L:
    for j in W_L:
        if data[i][j] == 1:
            for dx, dy in P:
                if 0 <= dx+i < H and 0 <= dy+j < W and data[dx+i][dy+j] == 1:
                        u, v = trans(i, j), trans(dx+i, dy+j)
                        G[u].append((v, 0))
                        G[v].append((u, 0))
            for dx, dy in DXY:
                if 0 <= dx+i < H and 0 <= dy+j < W and data[dx+i][dy+j] == 1:
                        u, v = trans(i, j), trans(dx+i, dy+j)
                        G[u].append((v, 1))
                        G[v].append((u, 1))


D = [10**6+100 for i in range(H*W)]
D[trans(ch-1, cw-1)] = 0
que = []
heapq.heapify(que)
heapq.heappush(que, (0, trans(ch-1, cw-1)))

while que:
    cost, v = heapq.heappop(que)
    if D[v] < cost:
        continue
    for node, cost in G[v]:
        if D[node] > D[v] + cost:
            D[node] = D[v] + cost
            heapq.heappush(que, (D[node], node))

ans = D[trans(dh-1, dw-1)]

if ans == 10**6+100:
    print(-1)
else:
    print(ans)

Solution (Python):
from collections import deque
import sys

H, W = map(int, input().split())
c_h, c_w = map(int, input().split())
d_h, d_w = map(int, input().split())
c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1
maze = []

for i in range(H):
    maze.append(list(input()))

check = [[-1 for i in range(W)] for j in range(H)]
number = 0

def bfs(sy, sx):
    global number
    check[sy][sx] = number
    d = deque([[sy, sx]])
    
    while d:
        y, x = d.popleft()
        
        for k, l in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            new_y, new_x = y + k, x + l
            
            if new_y < 0 or H <= new_y or new_x < 0 or W <= new_x:
                continue
            
            if check[new_y][new_x] != -1:
                continue
            
            if maze[new_y][new_x] == '
                continue
            
            d.append([new_y, new_x])
            check[new_y][new_x] = number
    
    number += 1
    
for i in range(H):
    for j in range(W):
        if check[i][j] == -1 and maze[i][j] == '.':
            bfs(i, j)


load = [[] for i in range(number)]
for i in range(H):
    for j in range(W):
        
        if check[i][j] != -1:
            
            for k in range(-2, 3):
                for l in range(-2, 3):
                    new_y, new_x = i + k, j + l
                    
                    if new_y < 0 or H <= new_y or new_x < 0 or W <= new_x:
                        continue
                    
                    f_num = check[i][j]
                    to_num = check[new_y][new_x]
                    
                    if to_num != -1 and to_num != f_num:
                        if not to_num in load[f_num]:
                            load[f_num].append(to_num)
                            load[to_num].append(f_num)

s_num = check[c_h][c_w]
g_num = check[d_h][d_w]

if s_num == g_num:
    print(0)
    sys.exit()

dp = [-1] * number
dp[s_num] = 0

d = deque([s_num])
ans = -1
flg = False
while d:
    if flg:
        break
    
    num = d.popleft()
    
    for i in load[num]:
        if i == g_num:
            ans = dp[num] + 1
            flg = True
            break
        
        if dp[i] != -1:
            continue
            
        dp[i] = dp[num] + 1
        d.append(i)
        
print(ans)

Solution (Python):
from heapq import heappop, heappush

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [input() for _ in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

a = [(-1, 0), (1, 0), (0, -1), (0, 1)]
b = [(i % 5 - 2, i // 5 - 2) for i in range(25) if (i % 5 - 2, i // 5 - 2) not in a]

d = [[H * W] * W for _ in range(H)]
d[Ch][Cw] = 0
Q = [(0, Ch, Cw)]
while Q:
    now_d, h, w = heappop(Q)
    if now_d > d[h][w]:
        continue
    if (h, w) == (Dh, Dw):
        break
    for ah, aw in a:
        nh, nw = h + ah, w + aw
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == ".":
            if d[nh][nw] > d[h][w]:
                d[nh][nw] = d[h][w]
                heappush(Q, (d[nh][nw], nh, nw))
    for ah, aw in b:
        nh, nw = h + ah, w + aw
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == ".":
            if d[nh][nw] > d[h][w] + 1:
                d[nh][nw] = d[h][w] + 1
                heappush(Q, (d[nh][nw], nh, nw))

if d[Dh][Dw] == H * W:
    ans = -1
else:
    ans = d[Dh][Dw]
print(ans)

Solution (Python):
from collections import deque
import sys, copy, itertools
input = sys.stdin.readline

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


MAP =[list(input().rstrip()) for i in range(h)]


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

MOVE = [[1,0],[-1,0],[0,1],[0,-1]]
JUMP = [[-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]]
STACK = deque([(ch,cw)])
STACKX = deque([(ch,cw)])


ans = -1 
MAP[ch][cw]=0


while STACKX:
  
  while STACK:
    y, x = STACK.popleft()
    for dy,dx in MOVE:
      ny = y + dy
      nx = x + dx
      if not(0 <= ny < h) or not(0 <= nx < w) or MAP[ny][nx]!='.':
        STACKX.append((y,x))
        continue
      else:
        STACK.append((ny,nx))
        MAP[ny][nx] = MAP[y][x]
   
  
  if MAP[dh][dw] != '.':
    ans = MAP[dh][dw]
  
  
  yy, xx = STACKX.popleft()
  for dyy,dxx in JUMP:
    nyy = yy + dyy
    nxx = xx + dxx
    if not(0 <= nyy < h) or not(0 <= nxx < w) or MAP[nyy][nxx]!='.':
      continue
    else:
      STACK.append((nyy,nxx))
      MAP[nyy][nxx] = MAP[yy][xx] + 1


      
      

print(ans)

Solution (Python):


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

h,w = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
b = read().split()

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



from collections import deque

def nbd(nh,nw,dv):
    if dv < res[nh][nw]:
        res[nh][nw] = dv
        q.appendleft((dv,nh,nw))
    return 




INF = 1<<30
res = [[INF]*w for _ in range(h)] 
res[sh][sw] = 0
q = deque([(0,sh,sw)]) 
while q:
    dv,vh,vw = q.popleft()
    if res[vh][vw] < dv: continue
    if vh==gh and vw==gw: break
    
    if vh and b[vh-1][vw]==".":
        nbd(vh-1,vw,dv)
    if vw and b[vh][vw-1]==".":
        nbd(vh,vw-1,dv)
    if vh+1<h and b[vh+1][vw]==".":
        nbd(vh+1,vw,dv)
    if vw+1<w and b[vh][vw+1]==".":
        nbd(vh,vw+1,dv)
    
    for i in range(-2,3):
        nh = vh+i
        if nh < 0 or nh >= h: continue
        for j in range(-2,3):
            nw = vw + j
            if nw < 0 or nw >= w: continue
            if abs(i)+abs(j) > 1:
                if b[nh][nw] == "." and dv+1 < res[nh][nw]:
                    res[nh][nw] = dv+1
                    q.append((dv+1,nh,nw))


ans = res[gh][gw]
if ans != INF:
    print(ans)
else:
    print(-1)

Solution (Python):
from collections import deque
H,W = map(int,input().split())
INF = 1000000
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
maze = []
maze.append(['
for i in range(H):
    maze.append(['
maze.append(['
dis = [[INF]*(W+2) for _ in range(H+2)]
d = deque()
nextd = []
dis[Ch][Cw] = 0
d.append((Ch,Cw))
dy = [0,1,0,-1]
dx = [1,0,-1,0]
cur = 0
while d:
    while d:
        y,x = d.popleft()
        if dis[y][x] == cur:
            for i in range(4):
                newy = y+dy[i]
                newx = x+dx[i]
                if maze[newy][newx] == '.':
                    if dis[newy][newx] > cur:
                        dis[newy][newx] = cur
                        d.append((newy,newx))
            for DY in range(-2,3):
                for DX in range(-2,3):
                    if abs(DX)+abs(DY) >= 2:
                        newy = y+DY
                        newx = x+DX
                        if newy <= H and newy >= 1 and newx <= W and newx >= 1: 
                            if maze[newy][newx] == '.':
                                if dis[newy][newx] > cur+1:
                                    dis[newy][newx] = cur+1
                                    nextd.append((newy,newx))
    cur += 1
    d = deque(nextd)
    nextd = []
if dis[Dh][Dw] == INF:
    print(-1)
else:
    print(dis[Dh][Dw])

Solution (Python):
from collections import deque
H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())

edge = [["
center = [["
A_array = edge + center + edge


cells_grouped = dict()
group_no = 1

edge = [[1 for _ in range(W+2)]]
center = [[1] + [0 for _ in range(W+2)] + [1] for i in range(H)] 
is_visited = edge + center + edge

edge = [[0 for _ in range(W+2)]]
center = [[0] + [0 for _ in range(W+2)] + [0] for i in range(H)] 
cell_group_dict = edge + center + edge

for i in range(1,H+1):
    for j in range(1,W+1):
        
        if is_visited[i][j] == 0:
            is_visited[i][j] = 1
            
            if A_array[i][j] == ".":
                
                search_target_deque = deque() 
                search_target_deque.append((i,j)) 
                grouped_cells = set()
                grouped_cells.add((i,j))

                while len(search_target_deque) != 0: 
                    m,n = search_target_deque.popleft() 
                    
                    cell_group_dict[m][n] = group_no
                    neighbor_nodes = [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]
                    for s,t in neighbor_nodes: 
                        if is_visited[s][t] == 0: 
                            is_visited[s][t] = 1 
                            if A_array[s][t] == ".":
                                search_target_deque.append((s,t)) 
                                grouped_cells.add((s,t))

                cells_grouped[group_no] = grouped_cells
                group_no += 1

                





                

warpable_group = {i:set() for i in range(group_no)}
for i in range(1,group_no):
    for cell in cells_grouped[i]:
        y = cell[0]
        x = cell[1]
        for m in range(y-2,y+3,1):
            if 1<=m<=H:
                for n in range(x-2,x+3,1):
                    if 1<=n<=W and cell_group_dict[m][n]!=0 and cell_group_dict[m][n]!=group_no:
                        warpable_group[i].add(cell_group_dict[m][n])





distance_from_start = ["?" for i in range(group_no)] 
is_visited = [0 for i in range(group_no)] 

v = cell_group_dict[Ch][Cw]

search_target_deque = deque() 
is_visited[v] = 1 
search_target_deque.append(v) 
distance_from_start[v] = 0

while len(search_target_deque) != 0: 
    node = search_target_deque.popleft() 
    
    if node == cell_group_dict[Dh][Dw]:
        print(distance_from_start[node])
        break
    
    near_nodes = warpable_group[node]
    
    for near_node in near_nodes: 

        if is_visited[near_node] == 0: 
            is_visited[near_node] = 1 
            search_target_deque.append(near_node) 
            distance_from_start[near_node] = distance_from_start[node] + 1
else:
    print(-1)

Solution (Python):
from collections import deque

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

moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
ts = [(x, y) for x in range(-2, 3)
      for y in range(-2, 3) if not (x, y) in moves and (x, y) != (0, 0)]

grid = [list(map(str, input().rstrip())) for _ in range(h)]

q = deque([(sx, sy)])
qq = deque([(sx, sy)])

grid[sx][sy] = 0

while len(q) > 0 or len(qq) > 0:
    while q:
        (cx, cy) = q.popleft()
        for m in moves:
            nx, ny = cx + m[0], cy + m[1]
            if 0 <= nx < h and 0 <= ny < w:
                if grid[nx][ny] == ".":
                    grid[nx][ny] = grid[cx][cy]
                    q.append((nx, ny))
                elif grid[nx][ny] == "
                    qq.append((cx, cy))
    while qq:
        (cx, cy) = qq.popleft()
        for t in ts:
            nx, ny = cx + t[0], cy + t[1]
            if 0 <= nx < h and 0 <= ny < w:
                if grid[nx][ny] == ".":
                    grid[nx][ny] = grid[cx][cy] + 1
                    q.append((nx, ny))

print(grid[gx][gy] if grid[gx][gy] != "." else -1)

Solution (Python):
from collections import deque
from collections import defaultdict

H, W = map(int, input().split())
ch, cw = map(int, input().split())
ch, cw = ch - 1, cw - 1  
dh, dw = map(int, input().split())
dh, dw = dh - 1, dw - 1  

S = []
for _ in range(H):
    S.append(list(input()))




G = []
for _ in range(H):
    G.append([-1] * W)


current_G = 0
group_dic = defaultdict(list)
for h in range(H):
    for w in range(W):
        if S[h][w] == '
            continue
        if G[h][w] != -1:
            continue
        G[h][w] = current_G
        group_dic[current_G].append((h, w))
        q = deque([(h, w)])
        while q:
            
            _h, _w = q.popleft()
            
            for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nx = _w + dx
                ny = _h + dy
                
                if nx < 0 or ny < 0 or nx >= W or ny >= H:
                    
                    continue
                if S[ny][nx] == '
                    continue
                if G[ny][nx] != -1:
                    
                    continue
                G[ny][nx] = current_G
                q.append((ny, nx))
                group_dic[current_G].append((ny, nx))
        current_G += 1





if current_G == 1:
    print(0)
    exit()


start_group = G[ch][cw]

P = [-1] * (current_G)
P[start_group] = 0


g = start_group
GG = deque([start_group])
while GG:
    g = GG.popleft()
    for h, w in group_dic[g]:
        for dx, dy in ((-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2),
                       (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2),
                       (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0),
                       (2, 1), (2, 2)):
            nx = w + dx
            ny = h + dy
            if nx < 0 or ny < 0 or nx >= W or ny >= H:
                continue
            if S[ny][nx] == '
                continue
            _g = G[ny][nx]
            if P[_g] != -1:
                continue
            P[_g] = P[g] + 1
            GG.append(_g)



ans = P[G[dh][dw]]
print(ans)

Solution (Python):
def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    Ch, Cw = (int(i)-1 for i in input().split())
    Dh, Dw = (int(i)-1 for i in input().split())
    A = [input() for i in range(H)]
    V = [[-1]*W for i in range(H)]  
    d = ((1, 0), (0, 1), (-1, 0), (0, -1))

    def bfs_2d(sy, sx, v):
        que = deque()
        V[sy][sx] = v
        que.append(sy * (H*W) + sx)
        while que:
            uh = que.popleft()
            uw = uh % (H*W)
            uh //= (H*W)
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if V[next_h][next_w] != -1:
                    continue
                if A[next_h][next_w] == '
                    continue
                V[next_h][next_w] = v
                que.append(next_h * (H*W) + next_w)

    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == "
                continue
            bfs_2d(h, w, vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == "
                continue
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))

    
    

    
    

    s = V[Ch][Cw]
    g = V[Dh][Dw]

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)

    print(dist[g])


if __name__ == '__main__':
    main()

Solution (Python):
H,W=map(int,input().split())

S=list(map(int,input().split()))
G=list(map(int,input().split()))
S[0]+=1
S[1]+=1
G[0]+=1
G[1]+=1

L=[]
l=[-1 for i in range(W+4)]
L.append(l)
L.append(l)
for i in range(H):
    s=list(input())
    for j in range(W):
        if s[j]=="
            s[j]=-1
        else:
            s[j]=10**12
    L.append([-1,-1]+s+[-1,-1])
L.append(l)
L.append(l)


X=[1,-1,0,0]
Y=[0,0,1,-1]
F=0
Q=[[S[0],S[1]]]

for x in range(10**6):
    if len(Q)==0:
        break
    for i in range(10**7):
        if i==len(Q):
            break
        H,W=Q[i]
        
        if L[H][W]==10**12:
            L[H][W]=x
            for xy in range(4):
                if L[H+X[xy]][W+Y[xy]]==10**12:
                    Q.append([H+X[xy],W+Y[xy]])
    q={}
    for i in range(len(Q)):
        H,W=Q[i]
        for h in range(-2,3):
            for w in range(-2,3):
                if L[H+h][W+w]==10**12:
                    q[(H+h,W+w)]=1
    
    Q=list(q.keys())
    
if L[G[0]][G[1]]==10**12:
    print(-1)
else:
    print(L[G[0]][G[1]])