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
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, combinations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from operator import itemgetter
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7
DEBUG = 'ONLINE_JUDGE' not in sys.argv

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):
    return fs[n] * invs[n-k] * invs[k] % modp



class UnionFindEx:
    def __init__(self, size):
        
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)

def main():
    H,W=mis()
    ch,cw=mis()
    ch-=1
    cw-=1
    dh,dw=mis()
    dh-=1
    dw-=1
    S = [input() for _ in range(H)]
    
    q = deque()
    nq = deque()
    q.append((ch, cw))
    reached = set()
    reached.add((ch, cw))
    zone = set()
    m = 0
    
    def isv(h, w):
        return (h, w) not in reached and 0<=h<H and 0<=w<W and S[h][w]=='.'
    
    while True:
        while q:
            h, w = q.popleft()
            zone.add((h, w))
            for nh, nw in ((h+1, w), (h-1, w), (h, w+1), (h, w-1)):
                if isv(nh, nw):
                    q.append((nh, nw))
                    reached.add((nh, nw))
        if (dh, dw) in reached:
            print(m)
            return
        for h, w in zone:
            for th in range(-2+h, 2+1+h):
                for tw in range(-2+w, 2+1+w):
                    if isv(th, tw):
                        nq.append((th, tw))
                        reached.add((th, tw))
        m += 1
        zone.clear()
        q, nq = nq, q
        if not q:
            print(-1)
            return







main()

Solution (Python):
from collections import deque

H,W = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))

F = [["
F += [["
F += [["
F += [["
F += [["

res = [[-1]*(W+4) for _ in range(H+4)]

Q = deque()
Q2 = deque()
Q.append([C[0]+1,C[1]+1])
Q2.append([C[0]+1,C[1]+1])
f_n = True
nd = ((0,1),(0,-1),(1,0),(-1,0))
bnum = 0

while f_n:
  f_n = False
  while len(Q)>0:
    x,y = Q.popleft()
    Q2.append([x,y])
    for dx,dy in nd:
      xx = x+dx
      yy = y+dy
      if F[xx][yy] == "." and res[xx][yy] == -1:
        Q.append([xx,yy])
        res[xx][yy] = bnum
  bnum += 1
  while len(Q2)>0:
    x,y = Q2.popleft()
    for i in range(-2,3):
      for j in range(-2,3):
        xx = x+i
        yy = y+j
        if F[xx][yy] == "." and res[xx][yy] == -1:
          Q.append([xx,yy])
          res[xx][yy] = bnum
          f_n = True
        

print(res[D[0]+1][D[1]+1])

Solution (Python):


from collections import deque
def main():
    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())
    S = [ input() for _ in range(H)]
    k = 10**7
    R = [ [k]*W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if S[i][j] == "
                R[i][j] = -1
    R[Ch][Cw] = 0
    T = [ [False]*W for _ in range(H)]
    d = deque([(Ch, Cw)])
    MW = [(-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 d:
        
        
        x, y = d.popleft()
        if T[x][y]:
            continue
        else:
            T[x][y] = True
        magic = R[x][y]
        if x == Dh and y == Dw:
            break
        if x > 0:
            if R[x-1][y] > magic:
                R[x-1][y] = magic
                d.appendleft((x-1,y))
        if x < H-1:
            if R[x+1][y] > magic:
                R[x+1][y] = magic
                d.appendleft((x+1,y))
        if y > 0:
            if R[x][y-1] > magic:
                R[x][y-1] = magic
                d.appendleft((x,y-1))
        if y < W-1:
            if R[x][y+1] > magic:
                R[x][y+1] = magic
                d.appendleft((x,y+1))
        for a, b in MW:
            tx, ty = x+a, y+b
            if tx < 0 or tx > H-1:
                continue
            if ty < 0 or ty > W-1:
                continue
            if R[tx][ty] > magic:
                R[tx][ty] = magic+1
                d.append((tx,ty))

    if R[Dh][Dw] == k:
        print(-1)
    else:
        print(R[Dh][Dw])
        
    
if __name__ == '__main__':
    main()

Solution (Python):
def main():

    H, W = map(int, input().split())
    h1, w1 = map(int, input().split())
    h2, w2 = map(int, input().split())
    h1 = h1-1
    w1 = w1-1
    h2 = h2-1
    w2 = w2-1
    S = []
    for _ in range(H):
        S.append(input())

    cur = [[h1, w1]]
    visited = set([(h1, w1)])
    vis = set([(h1, w1)])
    count = 0
    mv = [[-1, 0], [1, 0], [0, 1], [0, -1]]
    while cur:
        while cur:
            temp = []
            for h, w in cur:
                for i, j in mv:
                    x, y = h+i, w+j
                    if 0 <= x < H and 0<= y < W and (x, y) not in visited and S[x][y] == '.':
                        visited.add((x, y))
                        vis.add((x, y))
                        temp.append([x, y])
                        if (x, y) == (h2, w2):
                            return count
            cur = temp

        
        cur = []
        count += 1
        temp = set()
        for h, w in vis:
            for i in range(-2, 3):
                for j in range(-2, 3):
                    x, y = h+i, w+j
                    if 0 <= x < H and 0<= y < W and (x, y) not in visited and S[x][y] == '.':
                        cur.append([x, y])
                        visited.add((x, y))
                        temp.add((x, y))
                        if (x, y) == (h2, w2):
                            return  count
        
        vis = temp
    return -1


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

Solution (Python):


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

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

def isValid(h,w):
  if h>=0 and h<H and w>=0 and w<W and S[h][w]=='.' and A[h][w]==-1:
    return True
  else:
    return False

warp = 0
BFS_now = [(Ch-1, Cw-1)]
BFS_search = [(Ch-1, Cw-1)]
ij = [(-1,0),(0,-1),(0,1),(1,0)]
while len(BFS_now)>0:
  while len(BFS_search)>0:
    BFS_search_tmp = []
    for h,w in BFS_search:
      for i,j in ij:
        if isValid(h+i,w+j):
          BFS_search_tmp.append((h+i,w+j))
          A[h+i][w+j] = warp
    BFS_now += BFS_search_tmp
    BFS_search = BFS_search_tmp
  BFS_now_tmp = []
  for h,w in BFS_now:
    for i in range(-2,3):
      for j in range(-2,3):
        if isValid(h+i,w+j):
          BFS_now_tmp.append((h+i,w+j))
          A[h+i][w+j] = warp + 1
  BFS_now = BFS_now_tmp
  BFS_search = BFS_now_tmp
  warp += 1

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

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, C, D, S):

    C = (C[0]-1, C[1]-1)
    D = (D[0]-1, D[1]-1)
    q = deque()
    q.append((0, C))
    memo = {}
    while q:
        c, (x, y) = q.popleft()
        if (x, y) in memo:
            continue
        memo[(x, y)] = c
        for nx, ny in [(x, y-1), (x, y+1), (x-1, y), (x+1, y)]:
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if (nx, ny) not in memo:
                    q.appendleft((c, (nx, ny)))

        for nx in range(x-2, x+3):
            for ny in range(y-2, y+3):
                if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                    if (nx, ny) not in memo:
                        q.append((c+1, (nx, ny)))


    return -1 if tuple(D) not in memo else memo[D]


def main():
    H, W = read_int_n()
    C = read_int_n()
    D = read_int_n()
    S = [read_str() for _ in range(H)]
    print(slv(H, W, C, D, S))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

INF = 10**18

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

dist = [[None for j in range(W)] for i in range(H)]
dist[Ch][Cw] = 0

queue = deque()
queue.append((Ch, Cw))

while queue:
    x, y = queue.popleft()
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if dx == dy == 0:
                continue
            nx = x + dx
            ny = y + dy
            if not (0 <= nx < H and 0 <= ny < W):
                continue
            if S[nx][ny] == '
                continue
            if (dx == 0 and dy == 1) or (dx == 0 and dy == -1) or (dx == 1 and dy == 0) or (dx == -1 and dy == 0):
                if dist[nx][ny] == dist[x][y] + 1 or dist[nx][ny] is None:
                    dist[nx][ny] = dist[x][y]
                    queue.appendleft((nx, ny))
            else:
                if dist[nx][ny] is not None:
                    continue
                dist[nx][ny] = dist[x][y] + 1
                queue.append((nx, ny))

print(dist[Dh][Dw] if dist[Dh][Dw] is not None else -1)

Solution (Python):
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

grid = [[0 for _ in range(W)] for _ in range(H)]
grid[Ch][Cw] = 1

stack1 = [(Ch, Cw)]
stack2 = []

answer = 1



while 1:
    while stack1:
        sh, sw = stack1.pop()
    
        stack2.append((sh, sw))
    
        for i, j in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
            nh, nw = sh + i, sw + j
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != "
                if nh == Dh and nw == Dw:
                    print(answer - 1)
                    exit()
                grid[nh][nw] = answer
                stack1.append((nh, nw))
    
    
    if len(stack2) == 0:
        break
    
    answer += 1
    while stack2:
        sh, sw = stack2.pop()
        for i in range(-2, 3):
            for j in range(-2, 3):
                nh, nw = sh + i, sw + j
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != "
                    if nh == Dh and nw == Dw:
                        print(answer - 1)
                        exit()
                    grid[nh][nw] = answer
                    stack1.append((nh, nw))
    

print(-1)

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

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
state = [list(input().rstrip()) for _ in range(H)]

def nexts1(h, w):
    ret = []
    if h != 0: ret.append((h-1, w))
    if h != H-1: ret.append((h+1, w))
    if w != 0: ret.append((h, w-1))
    if w != W-1: ret.append((h, w+1))
    return ret

def nexts2(h, w):
    ret = []
    for nh in range(h-2, h+3):
        for nw in range(w-2, w+3):
            if 0 <= nh < H and 0 <= nw < W:
                ret.append((nh, nw))
    return ret


def bfs():
    checked = [[-1]*W for _ in range(H)]
    P = {(sh, sw)}
    cnt = 0
    while P:
        q = []
        for h, w in P:
            if checked[h][w] == -1:
                checked[h][w] = 1
                q.append((h, w))
        P = set()
        while q:
            qq = []
            for h, w in q:
                if h == gh and w == gw:
                    return cnt
                for nh, nw in nexts1(h, w):
                    if state[nh][nw] == ord(".") and checked[nh][nw] == -1:
                        checked[nh][nw] = checked[h][w]
                        qq.append((nh, nw))
                for nh, nw in nexts2(h, w):
                    if checked[nh][nw] == -1 and state[nh][nw] == ord(".") and not (nh, nw) in P:
                        P.add((nh, nw))
            q = qq
        cnt += 1
    return -1

def main():
    print(bfs())


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

int1 = lambda x: int(x) - 1

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

d = deque([(Ch, Cw)])
cur = 1
while True:
    visited = set()
    while d:
        h, w = d.pop()
        visited.add((h, w))
        S[h][w] = cur
        if (h, w) == (Dh, Dw):
            print(cur - 1)
            exit()
        for dh, dw in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            if 0 <= h + dh < H and 0 <= w + dw < W and S[h + dh][w + dw] == 0:
                d.append((h + dh, w + dw))

    for h, w in visited:
        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] == 0:
                    d.append((h + dh, w + dw))
    if not d:
        print(-1)
        exit()
    cur += 1

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import deque
from itertools import product
def resolve():
    m, n = map(int, input().split())
    si, sj = map(lambda x : int(x) - 1, input().split())
    ti, tj = map(lambda x : int(x) - 1, input().split())
    grid = [input() for _ in range(m)]

    queue = deque([(si, sj)])
    dist = [[INF] * n for _ in range(m)]
    dist[si][sj] = 0
    while queue:
        i, j = queue.popleft()
        for di, dj in product(range(-2, 3), repeat = 2):
            if di == dj == 0:
                continue
            ni, nj = i + di, j + dj
            if not (0 <= ni < m and 0 <= nj < n):
                continue
            if grid[ni][nj] == '
                continue
            dd = int(abs(di) + abs(dj) > 1)
            nd = dist[i][j] + dd
            if nd < dist[ni][nj]:
                dist[ni][nj] = nd
                if dd == 0:
                    queue.appendleft((ni, nj))
                else:
                    queue.append((ni, nj))


    ans = dist[ti][tj]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Solution (Python):
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
A = [[i for i in input()] for _ in range(H)]

visited = [[-1] * W for i in range(H)]
visited[Ch - 1][Cw - 1] = 0
h = [(Ch - 1, Cw - 1)]
c = 0
while True :
  done = []
  while h :
    cy, cx = h.pop()
    done.append((cy, cx))
    visited[cy][cx] = c
    for dy, dx in ((0, 1), (0, -1), (1, 0), (-1, 0)) :
      ny, nx = cy + dy, cx + dx
      if 0 <= ny < H and 0 <= nx < W and A[ny][nx] == '.' and visited[ny][nx] == -1 :
        h.append((ny, nx))
        visited[ny][nx] = c

  h = []
  for cy, cx in done :
    for dy in range(-2, 3) :
      for dx in range(-2, 3) :
        ny, nx = cy + dy, cx + dx
        if 0 <= ny < H and 0 <= nx < W and A[ny][nx] == '.' and visited[ny][nx] == -1 :
          h.append((ny, nx))
  if not h :
    break
  c += 1  
  
print(visited[Dh - 1][Dw - 1])

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    sh, sw = map(lambda x: int(x) - 1, input().split())
    gh, gw = map(lambda x: int(x) - 1, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]

    maze = [[f_inf] * W for _ in range(H)]
    maze[sh][sw] = 0
    que = deque([[sh, sw]])
    while que:
        h, w = que.popleft()
        for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            next_h, next_w = h + dh, w + dw
            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            if grid[next_h][next_w] == ".":
                if maze[next_h][next_w] > maze[h][w]:
                    maze[next_h][next_w] = maze[h][w]
                    que.appendleft([next_h, next_w])
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                next_h, next_w = h + dh, w + dw
                if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                    continue
                if grid[next_h][next_w] == ".":
                    if maze[next_h][next_w] > maze[h][w] + 1:
                        maze[next_h][next_w] = maze[h][w] + 1
                        que.append([next_h, next_w])
    print(maze[gh][gw] if maze[gh][gw] != f_inf else -1)


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import deque
H, W = map(int, input().split())
si, sj = map(int, input().split())
gi, gj = map(int, input().split())
si, sj, gi, gj = si+1, sj+1, gi+1, gj+1
X = [[1] * (W + 4)] * 2 + [[1] * 2 + [1 if a == "
H += 4
W += 4

Y = [(-1, 0), (0, -1), (0, 0), (0, 1), (1, 0)]
Z = [(-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)]

def BFS():
    Q = deque([(si, sj)])
    D = [-1] * (H * W)
    D[si*W + sj] = 0
    while Q:
        i, j = Q.popleft()
        x = i * W + j
        for di, dj in Y:
            ni, nj = i+di, j+dj
            y = ni * W + nj
            if X[ni][nj] == 0:
                if D[y] == -1 or D[y] > D[x]:
                    D[y] = D[x]
                    Q.appendleft((ni, nj))
        for di, dj in Z:
            ni, nj = i+di, j+dj
            y = ni * W + nj
            if X[ni][nj] == 0:
                if D[y] == -1:
                    D[y] = D[x] + 1
                    Q.append((ni, nj))
    return D[gi * W + gj]

print(BFS())

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

R, C = [int(x) for x in input().split()]
source = tuple([int(x) - 1 for x in input().split()])  
dest = tuple([int(x) - 1 for x in input().split()])  
grid = [input() for r in range(R)]


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


def getNbrGrid(node):
    r, c = node
    for dr, dc in drdc:
        nr = r + dr
        nc = c + dc
        if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '
            yield nr, nc



def bfs(source, getNbr):
    q = deque([source])
    dist = {source: 0}
    while q:
        node = q.popleft()
        d = dist[node]
        for nbr in getNbr(node):
            if nbr not in dist:
                q.append(nbr)
                dist[nbr] = d + 1
    return dist


numComps = 0
compId = {}
for r in range(R):
    for c in range(C):
        if grid[r][c] != "
            dist = bfs((r, c), getNbrGrid)
            for node in dist:
                compId[node] = numComps
            numComps += 1

if False:
    for r in range(R):
        for c in range(C):
            print(str(compId.get((r, c), ' ')).rjust(3), end="")
        print()

graph = defaultdict(set)
for r in range(R):
    for c in range(C):
        if grid[r][c] != '
            comp1 = compId[(r, c)]
            for dr in range(-2, 3):
                for dc in range(-2, 3):
                    nr = r + dr
                    nc = c + dc
                    if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '
                        comp2 = compId[(nr, nc)]
                        graph[comp1].add(comp2)

def getNbrComp(node):
    return graph[node]


if source not in compId or dest not in compId:
    print(-1)
    exit()
sourceComp = compId[source]
destComp = compId[dest]
dist = bfs(sourceComp, getNbrComp)
if destComp not in dist:
    print(-1)
    exit()
print(dist[destComp])

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 19 + 7
EPS = 10 ** -10

def build_grid(H, W, intv, _type, space=True, padding=False):
    
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def bfs(grid, src):
    """ BFS(グリッド、重みなし) """
    from collections import deque

    H, W = len(grid), len(grid[0])
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    dist = list2d(H, W, INF)
    que = deque()
    for h, w in src:
        que.append((h, w))
        dist[h][w] = 0
    while que:
        h, w = que.popleft()
        for dh, dw in directions:
            nh = h + dh
            nw = w + dw
            if grid[nh][nw] == '
                continue
            if dist[nh][nw] <= dist[h][w]:
                continue
            dist[nh][nw] = dist[h][w]
            que.appendleft((nh, nw))
        for nh in range(h-2, h+3):
            if nh < 0 or nh >= H:
                continue
            for nw in range(w-2, w+3):
                if nw < 0 or nw >= W:
                    continue
                if grid[nh][nw] == '
                    continue
                if dist[nh][nw] <= dist[h][w] + 1:
                    continue
                dist[nh][nw] = dist[h][w] + 1
                que.append((nh, nw))
    return dist

H, W = MAP()
sh, sw = MAP()
th, tw = MAP()
grid = build_grid(H, W, '

res = bfs(grid, [(sh, sw)])
ans = res[th][tw]
if ans == INF:
    print(-1)
else:
    print(ans)

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


def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    
    s = [input().replace("\n", "") for _ in range(h)]
    
    ans = [[-1]*w for _ in range(h)]
    ans[ch-1][cw-1] = 0
    not_yet = deque([(ch-1, cw-1)])
    one_time = deque([])
    while not_yet:
        x, y = not_yet.popleft()
        one_time.append((x, y))
        if x > 0 and ans[x-1][y] == -1 and s[x-1][y] == ".":
            not_yet.append((x-1, y))
            ans[x-1][y] = ans[x][y]
        if x < h-1 and ans[x+1][y] == -1 and s[x+1][y] == ".":
            not_yet.append((x+1, y))
            ans[x+1][y] = ans[x][y]
        if y > 0 and ans[x][y-1] == -1 and s[x][y-1] == ".":
            not_yet.append((x, y-1))
            ans[x][y-1] = ans[x][y]
        if y < w-1 and ans[x][y+1] == -1 and s[x][y+1] == ".":
            not_yet.append((x, y+1))
            ans[x][y+1] = ans[x][y]
        if not not_yet:
            while one_time:
                x2, y2 = one_time.popleft()
                for i in range(max(0, x2-2), min(h, x2+3)):
                    for j in range(max(0, y2-2), min(w, y2+3)):
                        if ans[i][j] == -1 and s[i][j] == ".":
                            ans[i][j] = ans[x][y]+1
                            not_yet.append((i, j))

    print(ans[dh-1][dw-1])
            
            
            
        
    
    
    
    
if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import heapq
    inf = 10**8
    h, w = map(int, input().split())
    start = list(map(int, input().split()))
    goal = list(map(int, input().split()))
    start = (start[0]-1, start[1]-1)
    goal = (goal[0]-1, goal[1]-1)
    grid = [input() for _ in [0]*h]
    dist = [[inf]*w for _ in [0]*h]
    q = [(0, start)]
    dist[start[0]][start[1]] = 0
    heapq.heapify(q)
    while q:
        d, (nowx, nowy) = heapq.heappop(q)
        for i, j in [(nowx-1, nowy), (nowx+1, nowy), (nowx, nowy-1), (nowx, nowy+1)]:
            if i < 0 or i >= h or j < 0 or j >= w:
                continue
            if grid[i][j] == "
                continue
            if dist[i][j] > d:
                dist[i][j] = d
                heapq.heappush(q, (d, (i, j)))
        for i in range(nowx-2, nowx+3):
            for j in range(nowy-2, nowy+3):
                if i < 0 or i >= h or j < 0 or j >= w:
                    continue
                if grid[i][j] == "
                    continue
                if dist[i][j] > d+1:
                    dist[i][j] = d+1
                    heapq.heappush(q, (d+1, (i, j)))
    if dist[goal[0]][goal[1]] == inf:
        print(-1)
        return
    print(dist[goal[0]][goal[1]])


main()

Solution (Python):
INF=float('inf')
from collections import deque
def mbfs(G,sh,sw,H,W):
    dist=[[INF]*W for i in range(H)]
    dist[sh][sw]=0

    d=deque()
    d.append([sh,sw])
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        d.popleft()
        for dir in range(4):
            nh=h+dx[dir]
            nw=w+dy[dir]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(G[nh][nw]=='
                continue
            if dist[nh][nw]>dist[h][w]:
                dist[nh][nw]=dist[h][w]
                d.appendleft([nh,nw])
        for i in range(h-2,h+3):
            for j in range(w-2,w+3):
                if (i>H-1 or i<0 or j>W-1 or j<0):
                    continue
                if (G[i][j]=='
                    continue
                if dist[i][j]>dist[h][w]+1:
                    dist[i][j]=dist[h][w]+1
                    d.append([i,j])
    return dist

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())
G=[list(input()) for i in range(H)]

dist=mbfs(G,Ch,Cw,H,W)
if dist[Dh][Dw]!=INF:
    print(dist[Dh][Dw])
else:
    print(-1)