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
input = sys.stdin.readline

H, W = map(int, input().split())
Cy, Cx = map(int, input().split())
Dy, Dx = map(int, input().split())
Board = [input().rstrip() for _ in range(H)]







Cy -= 1
Cx -= 1
Dy -= 1
Dx -= 1

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
vst = [[-1] * W for _ in range(H)]

def BFS(y, x, C):
    vst[y][x] = C
    q = [(x, y)]
    for x1, y1 in q:
        for i in range(4):
            x2 = x1 + dx[i]
            y2 = y1 + dy[i]
            if 0 <= x2 < W and 0 <= y2 < H and vst[y2][x2] < 0 and Board[y2][x2] == '.':
                vst[y2][x2] = C
                q.append((x2, y2))

count = 0
for i in range(H):
    for j in range(W):
        if vst[i][j] < 0 and Board[i][j] == '.':
            BFS(i, j, count)
            count += 1




adj = [set() for _ in range(count)]
vst_g = [False] * count

for i in range(H):
    for j in range(W):
        if Board[i][j] == '.':
            cur = vst[i][j]
            for x in [-2, -1, 0, 1, 2]:
                for y in [-2, -1, 0, 1, 2]:
                    x1 = x + j
                    y1 = y + i
                    if 0 <= x1 < W and 0 <= y1 < H and Board[y1][x1] == '.':
                        if vst[y1][x1] != cur:
                            adj[cur].add(vst[y1][x1])



vst_g = [-1] * count
vst_g[vst[Cy][Cx]] = 0
q = [vst[Cy][Cx]]


for u in q:
    for v in adj[u]:
        if vst_g[v] < 0:
            vst_g[v] = vst_g[u] + 1
            q.append(v)

print(vst_g[vst[Dy][Dx]])

Solution (Python):
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)]

Ch,Cw=Ch-1,Cw-1
Dh,Dw=Dh-1,Dw-1
todo=[[0,Ch,Cw]]
ntodo=[]
d=[[-1]*w for _ in range(h)]
d[Ch][Cw]=0
toho=[[0,1],[0,-1],[1,0],[-1,0]]
wiz=[[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]]
while todo or ntodo:
  if not todo:
    todo=ntodo
    ntodo=[]
  cnt,nh,nw=todo.pop()
  if d[nh][nw]<cnt:continue
  for dh,dw in toho:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt:
        d[nh+dh][nw+dw]=cnt
        todo.append([cnt,nh+dh,nw+dw])
  for dh,dw in wiz:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt+1:
        d[nh+dh][nw+dw]=cnt+1
        ntodo.append([cnt+1,nh+dh,nw+dw])
print(d[Dh][Dw])

Solution (Python):
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

def main():
    direction=[[1,0],[0,1],[-1,0],[0,-1]]


    h,w=map(int,input().split())
    c=tuple(map(int,input().split()))
    d=tuple(map(int,input().split()))
    s=[input() for i in range(h)]

    itta=[[-1]*w for i in range(h)]
    itta[c[0]-1][c[1]-1]=0
    de=deque([(c[0]-1,c[1]-1)])
    
    cnt=0
    while de:
        lst=[]
        while de:
            now=de.popleft()
            flag=0
            for i in range(4):
                nh,nw=now[0]+direction[i][0],now[1]+direction[i][1]
                if 0<=nh<h and 0<=nw<w:
                    if itta[nh][nw]==-1 and s[nh][nw]==".":
                        itta[nh][nw]=cnt
                        de.append((nh,nw))
                    elif s[nh][nw]=="
                        flag=1
                        lst.append(now)
        
        for i in range(len(lst)):
            for j in range(5):
                for k in range(5):
                    nh,nw=lst[i][0]-2+j,lst[i][1]-2+k
                    if 0<=nh<h and 0<=nw<w and s[nh][nw]=="." and itta[nh][nw]==-1:
                        itta[nh][nw]=cnt+1
                        de.append((nh,nw,cnt+1))
        cnt+=1
    print(itta[d[0]-1][d[1]-1])

main()

Solution (Python):

import sys
input = sys.stdin.readline
import heapq
INF = 10**9

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
        return self.dist

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
field = []
block_num = 0
for _ in range(h):
    line = input().rstrip()
    field.append(line)
    block_num += line.count("
if h * w == 10**6 and block_num < 1000:
    print(0)
    exit()

edge = [[] for _ in range(h * w)]
for i in range(h):
    for j in range(w):
        if field[i][j] == "
            continue
        frm = i * w + j
        for dx in range(-2, 3):
            nx = i + dx
            if nx < 0 or nx > h - 1:
                continue
            for dy in range(-2, 3):
                if dx == 0 and dy == 0:
                    continue
                ny = j + dy
                if ny < 0 or ny > w - 1:
                    continue
                if field[nx][ny] == "
                    continue
                dist = abs(dx) + abs(dy)
                if dist == 1:
                    edge[frm].append((nx*w + ny, 0))
                else:
                    edge[frm].append((nx*w + ny, 1))
        
DIJK = Dijkstra(edge)
dist = DIJK.calc(ch * w + cw)
if dist[dh * w + dw] == INF:
    print(-1)
else:
    print(dist[dh * w + dw])

Solution (Python):
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    H, W = read_values()
    C = tuple(read_index())
    D = tuple(read_index())
    S = [input().strip() for _ in range(H)]

    F = [False] * (H * W)

    M = {C}
    Q = [C]
    F[C[0] * W + C[1]] = 0
    c = 0
    while len(M) > 0:
        M.clear()
        while Q:
            h, w = Q.pop()
            M.add((h, w))
            if (h, w) == D:
                print(c)
                return

            for d in (1, -1):
                if 0 <= w + d < W and S[h][w + d] == "." and not F[h * W + w + d]:
                    F[h * W + w + d] = True
                    Q.append((h, w + d))
                if 0 <= h + d < H and S[h + d][w] == "." and not F[(h + d) * W + w]:
                    F[(h + d) * W + w] = True
                    Q.append((h + d, w))
        for h, w in M:
            for hh in range(h - 2, h + 3):
                for ww in range(w - 2, w + 3):
                    if 0 <= ww < W and 0 <= hh < H and S[hh][ww] == "." and not F[hh * W + ww]:
                        F[hh * W + ww] = True
                        Q.append((hh, ww))
        c += 1
    print(-1)
            

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
H,W = [int(hoge) for hoge in input().split()]
curh,curw = [int(hoge)-1 for hoge in input().split()]
gh,gw = [int(hoge)-1 for hoge in input().split()]
S = [input() for _ in range(H)]

Dist = [[999999 for w in range(W)] for h in range(H)]
Dist[curh][curw] = 0
BFS = deque()
BFS.append((curh,curw))
while BFS:
    curh,curw = BFS.popleft()
    for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
        if 0<=curh+dx<H and 0<=curw+dy<W and S[curh+dx][curw+dy]==".":
            if Dist[curh+dx][curw+dy] > Dist[curh][curw]:
                Dist[curh+dx][curw+dy] = Dist[curh][curw]
                BFS.appendleft((curh+dx,curw+dy))

  

    for dx in range(-2,3):
        for dy in range(-2,3):
            if 0<=curh+dx<H and 0<=curw+dy<W and  S[curh+dx][curw+dy]==".":
                if Dist[curh+dx][curw+dy] > Dist[curh][curw] + 1:
                    Dist[curh+dx][curw+dy] = Dist[curh][curw]+1
                    BFS.append((curh+dx,curw+dy))
ans = Dist[gh][gw]
if ans == 999999:
    ans = -1
print(ans)

Solution (Python):
h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch -= 1
cw -= 1
dh,dw = map(int,input().split())
dh -= 1
dw -= 1
s = [input() for _ in range(h)]

def newv(y,x):
  return y*w+x

e = [[] for _ in range(h*w)]
for y in range(h):
  for x in range(w):
    if s[y][x] == '
      continue
    for dy in range(-2,3):
      for dx in range(-2,3):
        if not(0 <= y+dy < h) or not(0 <= x+dx < w):
          continue
        if dy == 0 and dx == 0:
          continue
        if abs(dy)+abs(dx) == 1:
          if s[y+dy][x+dx] == '.':
            e[newv(y,x)].append((newv(y+dy,x+dx),0))
        else:
          if s[y+dy][x+dx] == '.':
            e[newv(y,x)].append((newv(y+dy,x+dx),1))

from heapq import heappop, heappush
INF = float('inf')
def dijkstra(s,n,g): 
  que = []
  d = [INF for _ in range(n)]
  d[s] = 0
  heappush(que,(0,s))
  while len(que) > 0:
    p = heappop(que)
    v = p[1]
    if d[v] < p[0]:
      continue
    for u,w in g[v]:
      if d[u] > d[v]+w:
        d[u] = d[v]+w
        heappush(que,(d[u],u))
  return d

ans = dijkstra(newv(ch,cw),h*w,e)[newv(dh,dw)]
print(ans if ans != INF else -1)

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

dxdy4 = ((-1, 0), (0, -1), (0, 1), (1, 0))


def main():
    H, W = map(int, readline().split())
    Ch, Cw = map(int, readline().split())
    Dh, Dw = map(int, readline().split())
    S = [readline().strip() for _ in range(H)]

    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    grid = [[-1] * W for _ in range(H)]
    n = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] != -1 or S[i][j] == '
                continue
            grid[i][j] = n
            queue = deque([(i, j)])
            while queue:
                x, y = queue.popleft()
                for dx, dy in dxdy4:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == -1 and S[nx][ny] == '.':
                        grid[nx][ny] = n
                        queue.append((nx, ny))
            n += 1

    if grid[Ch][Cw] == grid[Dh][Dw]:
        print(0)
        return

    G = [set() for _ in range(n)]
    for i in range(H):
        for j in range(W):
            if grid[i][j] == -1:
                continue
            this_num = grid[i][j]
            for dx in range(-2, 3, 1):
                for dy in range(-2, 3, 1):
                    nx, ny = i + dx, j + dy
                    if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] not in (-1, this_num):
                        G[this_num].add(grid[nx][ny])
                        G[grid[nx][ny]].add(this_num)

    queue = deque([grid[Ch][Cw]])
    dist = [-1] * n
    dist[grid[Ch][Cw]] = 0
    while queue:
        v = queue.popleft()
        for nv in G[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                queue.append(nv)

    print(dist[grid[Dh][Dw]])
    return


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

h, w = map(int, input().split())
C = list(map(int, input().split()))
C = tuple([C[0]-1, C[1]-1])
D = tuple(map(int, input().split()))
D = tuple([D[0]-1, D[1]-1])
maze = [list(input()) for _ in range(h)]

visit = [[False]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if maze[i][j] == "
            visit[i][j] = True

DQ = deque([C])
DQ_warp = deque([])

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

ans = 0

while DQ or DQ_warp:
    while DQ:
        now = DQ.popleft()
        if now == D:
            print(ans)
            exit()
        x, y = now[0], now[1]
        if visit[x][y]:
            continue
        visit[x][y] = True
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<=h-1 and 0<=ny<=w-1 and visit[nx][ny]==False:
                DQ.append(tuple([nx, ny]))

        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == j == 0: continue
                nx = x + i
                ny = y + j
                if 0<=nx<=h-1 and 0<=ny<=w-1 and visit[nx][ny]==False:
                    DQ_warp.append(tuple([nx, ny]))

    if DQ_warp:
        DQ = DQ_warp.copy()
        DQ_warp = deque([])
        ans += 1

print(-1)

Solution (Python):
def examA():
    N, X, T = LI()
    ans = (1 + (N-1)//X)*T
    print(ans)
    return

def examB():
    N = SI()
    s = 0
    for n in N:
        s += int(n)
    if s%9==0:
        ans = "Yes"
    else:
        ans = "No"
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    now = A[0]
    cnt = 0
    for i in range(N):
        if now>A[i]:
            cnt += now-A[i]
        if now<A[i]:
            now = A[i]
    ans = cnt
    print(ans)
    return

def examD():
    def bfs_grid(h, w, s, g, maze):
        distance = [[inf] * w for _ in range(h)]

        def bfsg():
            queue = deque()
            queue.append(s)
            cost = 0
            distance[s[0]][s[1]] = cost
            used = [s]
            while(True):
                while len(queue):
                    y, x = queue.popleft()
                    for i in range(4):
                        nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '
                            if distance[ny][nx] != inf:
                                continue
                            queue.append((ny, nx))
                            distance[ny][nx] = cost
                            used.append((ny,nx))

                

                if distance[g[0]][g[1]]==inf:
                    cost += 1
                    used_ne = []
                    for y,x in used:
                        for i in range(5):
                            nx = x + [-2, -1, 0, 1, 2][i]
                            if not 0<=nx<W:
                                continue
                            for j in range(5):
                                ny = y + [-2, -1, 0, 1, 2][j]
                                if not 0<=ny<H:
                                    continue
                                if distance[ny][nx] != inf:
                                    continue
                                if maze[ny][nx]=="
                                    continue
                                queue.append((ny,nx))
                                distance[ny][nx] = cost
                                used_ne.append((ny,nx))
                    used = used_ne

                    if not queue:
                        
                        return -1
                    continue

                return cost


            return distance

        return bfsg()
    H, W = LI()
    C = LI()
    D = LI()
    C[0] -= 1; C[1] -= 1
    D[0] -= 1; D[1] -= 1
    S = [SI()for _ in range(H)]
    ans = bfs_grid(H, W, C, D, S)
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
from collections import deque
h, w = map(int, input().split())
a, b = map(int, input().split())
c, d = map(int, input().split())
a -= 1
b -= 1
c -= 1
d -= 1
s = [list(input()) for i in range(h)]
now = 0
dd = [(-1, 0), (1, 0), (0, 1), (0, -1)]

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            de = deque([(i, j)])
            s[i][j] = now
            while de:
                x, y = de.popleft()
                for p, q in dd:
                    if 0 <= x + p < h and 0 <= y + q < w and s[x + p][y + q] == ".":
                        s[x + p][y + q] = now
                        de.append((x + p, y + q))
            now += 1
st = s[a][b]
en = s[c][d]
es = [set() for i in range(now)]
for i in range(h):
    for j in range(w):
        if s[i][j] != "
            for p in range(-2, 3):
                for q in range(-2, 3):
                    if 0 <= i + p < h and 0 <= j + q < w and s[i + p][j + q] != "
                        es[s[i][j]].add(s[i + p][j + q])
                        es[s[i + p][j + q]].add(s[i][j])
from heapq import heappush, heapify, heappop


def dijkstra(s):
    INF = 1 << 32
    d = [INF] * now  
    v = -1
    que = [(0, s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in es[v]:
            if d[e] > d[v] + 1:
                d[e] = d[v] + 1
                heappush(que, (d[e], e))
    return d[en] if d[en] < INF else -1


print(dijkstra(st))

Solution (Python):
def dfs(x,y,visited,grid,dp,r,c,n):
    stack = [(x,y)]
    k = 0
    while k < len(stack):
        x,y = stack[k]
        if (x,y) not in visited:
            dp[x][y] = n
            visited.add((x,y))
            if x+1 < r and grid[x+1][y] == '.':
                stack.append((x+1,y))

            if y+1 < c and grid[x][y+1] == '.':
                stack.append((x,y+1))

            if x-1 >= 0 and grid[x-1][y] == '.':
                stack.append((x-1,y))

            if y-1 >= 0 and grid[x][y-1] == '.':
                stack.append((x,y-1))

        k += 1

def shortestPath(x,y,edges):
    stack = [(x,0)]
    visited = set()
    k = 0
    while k < len(stack):
        x,d = stack[k]
        if x not in visited:
            visited.add(x)
            if x == y:
                print(d)
                return
            
            for kid in edges[x]:
                stack.append((kid,d+1))

        k += 1

    print(-1)

def main():
    r,c = map(int,input().split())
    x1,y1 = map(int,input().split())
    x2,y2 = map(int,input().split())
    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1
    dp = [[0 for j in range(c)] for i in range(r)]
    grid = []
    for i in range(r):
        grid.append(input())

    visited = set()
    n = 1
    for i in range(r):
        for j in range(c):
            if (i,j) not in visited and grid[i][j] == '.':
                dfs(i,j,visited,grid,dp,r,c,n)
                n += 1

    edges = {}
    for i in range(1,n):
        edges[i] = set()

    for i in range(r):
        for j in range(c):
            if grid[i][j] == '.':
                x = dp[i][j]
                for k in range(max(0,i-2),min(r,i+3)):
                    for l in range(max(0,j-2),min(c,j+3)):
                        y = dp[k][l]
                        if x != y and y != 0:
                            edges[x].add(y)
                            edges[y].add(x)

    x = dp[x1][y1]
    y = dp[x2][y2]
    shortestPath(x,y,edges)

main()

Solution (Python):
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()

def main():
    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 = [input() for _ in range(H)]

    repn = [[] for _ in range(H * W)]  
    for h in range(H):
        for w in range(W):
            if S[h][w] != '.': continue
            if w > 0 and S[h][w - 1] == '.':
                repn[h * W + w].append((0, h * W + w - 1))
            if w < W - 1 and S[h][w + 1] == '.':
                repn[h * W + w].append((0, h * W + w + 1))
            if h > 0 and S[h - 1][w] == '.':
                repn[h * W + w].append((0, (h - 1) * W + w))
            if h < H - 1 and S[h + 1][w] == '.':
                repn[h * W + w].append((0, (h + 1) * W + w))

            for ph in range(5):
                for pw in range(5):
                    if abs(ph - 2) + abs(pw - 2) <= 1: continue
                    nh = h + ph - 2
                    nw = w + pw - 2
                    if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                        repn[h * W + w].append((1, nh * W + nw))

    q = [(0, ch * W + cw)]
    visited = [10**18] * (H * W)
    visited[ch * W + cw] = 0
    while q:
        cost, u = heappop(q)
        if visited[u] < cost: continue
        for dcost, nu in repn[u]:
            if visited[nu] > cost + dcost:
                visited[nu] = cost + dcost
                heappush(q, (cost + dcost, nu))

    ans = visited[dh * W + dw]
    if ans == 10**18:
        print(-1)
    else:
        print(ans)





if __name__ == "__main__":
    main()

Solution (Python):
import sys

def input():
    return sys.stdin.readline()[:-1]
def smax(a,b):
    if a>b:
        return a
    else:
        return b

def smin(a,b):
    if a<b:
        return a
    else:
        return b

from collections import deque

def BFS(vi,c,e_list,color_list):
        
    Q = deque([vi])
    color_list[vi] = c
    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if color_list[v1]==-1:
                color_list[v1]=c
                Q.appendleft(v1)



def main():
    H,W = list(map(int,input().split()))
    s1,s2 = list(map(int,input().split()))
    g1,g2 = list(map(int,input().split()))
    s1,s2 = s1-1,s2-1
    g1,g2 = g1-1,g2-1
    S = [input() for i in range(H)]

    def z(i,j):
        return i*W + j

    e_list = [[] for i in range(H*W)]

    for i in range(H):
        for j in range(W):
            if i!=H-1:
                if S[i][j]=="." and S[i+1][j]==".":
                    e_list[z(i,j)].append(z(i+1,j))
                    e_list[z(i+1,j)].append(z(i,j))
            if j!=W-1:
                if S[i][j]=="." and S[i][j+1]==".":
                    e_list[z(i,j)].append(z(i,j+1))
                    e_list[z(i,j+1)].append(z(i,j))

    color_list = [-1]*(H*W)
    c = 0


    for i in range(H*W):
        if S[i//W][i%W] == ".":
            if color_list[i]==-1:
                BFS(i,c,e_list,color_list)
                c+=1

    comp = max(color_list)+1
    e_list = [set([]) for i in range(comp)]


    for x in range(H*W):
        i,j = x//W,x%W
        if color_list[x]!=-1:
            for y in range(25):
                i1,j1 = y//5,y%5
                i2 = i1 + i - 2
                j2 = j1 + j - 2
                if 0<=i2 and i2<=H-1 and 0<=j2 and j2<=W-1:
                    if color_list[z(i2,j2)]!=-1 and color_list[z(i2,j2)]!=color_list[x]:
                        e_list[color_list[z(i2,j2)]].add(color_list[x])
                        e_list[color_list[x]].add(color_list[z(i2,j2)])

    vi = color_list[z(s1,s2)]  
    INF = float('inf')
    N = comp
    Q = deque([vi])

    checked_list = [False]*N
    checked_list[vi]=True

    min_path_list = [INF]*N 
    min_path_list[vi] = 0
    
    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if not checked_list[v1]:
                checked_list[v1]=True
                Q.appendleft(v1)
                min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) 
    if min_path_list[color_list[z(g1,g2)]]<=10**26:
        print(min_path_list[color_list[z(g1,g2)]])
    else:
        print(-1)

if __name__ == '__main__':
    main()

Solution (Python):
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
dydx4 = ((-1,0),(0,-1),(0,1),(1,0))
def check(i,j):
  return 0 <= i < h and 0 <= j < w 
def on_block(i,j):
  return S[i][j] == "
h,w = map(int,input().split())
ci,cj = map(int,input().split())
ci-=1;cj-=1
gi,gj = map(int,input().split())
gi-=1;gj-=1
S = [list(input()) for i in range(h)]
grid = [[inf] * w for i in range(h)]
grid[ci][cj] = 0
que = collections.deque()
que.append((0,ci,cj))
while que:
  now,si,sj = que.popleft()
  if now > grid[si][sj]:continue
  for di,dj in dydx4:
    ni = si + di
    nj = sj + dj
    if not check(ni,nj):continue
    if on_block(ni,nj): continue
    else:
      if now < grid[ni][nj] :
        grid[ni][nj] = now
        que.appendleft((now,ni,nj))
        
  for i in range(si-2,si+3):
    for j in range(sj-2,sj+3):
      if not check(i,j):continue
      if on_block(i,j):continue
      else:
        if now + 1 < grid[i][j] :
          grid[i][j] = now + 1
          que.append((now+1,i,j))
          
print(grid[gi][gj] if grid[gi][gj] != inf else -1)

Solution (Python):
def bsf_dist_grid(grid,start):
    H = len(grid)
    W = len(grid[0])
    d = [[-1]*W for _ in [0]*H]
    d[start[0]][start[1]] = 0
    q = [start[::-1]]
    while q:
        qq = []
        for xy in q:
            x,y = xy
            d0 = d[y][x]
            for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
                if (not 0<=x+dx<W) or (not 0<=y+dy<H): continue
                if d[y+dy][x+dx] != -1: continue
                if not grid[y+dy][x+dx]: continue
                d[y+dy][x+dx] = d0
                q.append((x+dx,y+dy))
            for dx,dy in ((2,0),(2,1),(2,2),(2,-1),(2,-2),(1,2),(1,1),(1,-1),(1,-2),(0,2),(0,-2),(-1,2),(-1,1),(-1,-1),(-1,-2),(-2,2),(-2,1),(-2,0),(-2,-1),(-2,-2)):
                if (not 0<=x+dx<W) or (not 0<=y+dy<H): continue
                if d[y+dy][x+dx] != -1: continue
                if not grid[y+dy][x+dx]: continue
                qq.append(((x+dx,y+dy),d0+1))
        q = []
        for qq2,d2 in qq:
            x,y = qq2
            if d[y][x] != -1: continue
            d[y][x] = d2
            q.append(qq2)
    return d

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
s = [[c=="." for c in input()] for _ in [0]*H]

d = bsf_dist_grid(s,(Ch-1,Cw-1))

print(d[Dh-1][Dw-1])

Solution (Python):
import sys
my_input = sys.stdin.readline
from collections import deque
H, W = map(int, my_input().split())
Sh, Sw = map(int, my_input().split())
Sh, Sw = Sh - 1, Sw - 1
Gh, Gw = map(int, my_input().split())
Gh, Gw = Gh - 1, Gw - 1
G = [list(my_input()) for _ in range(H)]
INF = 10 ** 9

dist = [[INF] * W for _ in range(H)]
dist[Sh][Sw] = 0
que = deque([[Sh, Sw]])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
directions5 = []
for i in range(-2, 3):
    for j in range(-2, 3):
        directions5.append((i, j))


while que:
    nh, nw = que.pop()
    for dh, dw in directions:
        fh, fw = nh + dh, nw + dw
        if not ((0 <= fh < H) and (0 <= fw < W)):
            continue
        if G[fh][fw] == '
            continue
        if dist[fh][fw] <= dist[nh][nw]:
            continue
        dist[fh][fw] = dist[nh][nw]
        que.append([fh, fw])

    for dh, dw in directions5:
        fh, fw = nh + dh, nw + dw
        if not ((0 <= fh < H) and (0 <= fw < W)):
            continue
        if G[fh][fw] == '
            continue
        if dist[fh][fw] <= dist[nh][nw] + 1:
            continue
        dist[fh][fw] = dist[nh][nw] + 1
        que.appendleft([fh, fw])

print(dist[Gh][Gw] if dist[Gh][Gw] != INF else - 1)