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
import itertools

import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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 = [0] * H
for i in range(H):
    S[i] = input()

q = deque([])
dist = [[-1] * W for _ in range(H)]
q.append((ch, cw, 0))
dist[ch][cw] = 0
while len(q) > 0:
    cur = []
    while len(q) > 0:
        cy, cx, d = q.popleft()
        cur.append((cy, cx, d))
        for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = cy + dy
            x = cx + dx
            if y < 0 or y >= H or x < 0 or x >= W:
                continue
            if S[y][x] == '
                continue
            if dist[y][x] != -1:
                continue
            dist[y][x] = dist[cy][cx]
            q.appendleft((y, x, d))
    for cy, cx, d in cur:
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                y = cy + dy
                x = cx + dx
                if y < 0 or y >= H or x < 0 or x >= W:
                    continue
                if S[y][x] == '
                    continue
                if dist[y][x] != -1:
                    continue
                dist[y][x] = d + 1
                q.appendleft((y, x, d + 1))
print(dist[dh][dw])

Solution (Python):
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
WarpX = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
WarpY = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]

que = deque([(ch, cw)])
que2 = deque()
while que or que2:
    while que:
        y, x = que.popleft()
        for i in range(4):
            ny = y + NY[i]
            nx = x + NX[i]
            if 0 <= ny < h and 0 <= nx < w:
                if S[ny][nx] != "
                    grid[ny][nx] = grid[y][x]
                    que.append((ny, nx))
                elif S[ny][nx] == "
                    que2.append((y, x))
    while que2:
        y, x = que2.popleft()
        for i in range(20):
            ny = y + WarpY[i]
            nx = x + WarpX[i]
            if 0 <= ny < h and 0 <= nx < w:
                if S[ny][nx] != "
                    grid[ny][nx] = grid[y][x] + 1
                    que.append((ny, nx))

print(grid[dh][dw])

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


import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8))
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] 
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
rows,cols = h,w

OK = "."
NG = "

ss = np.array([[c=="

print(main(ss,ch,cw,dh,dw))

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

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

start = (Ch, Cw)

S = ['
S.append('
for k in range(H):
  S.append('
S.append('
S.append('

counter = [[-1 for _ in range(W+4)] for _ in range(H+4)]
for k in range(2, H+2):
  for j in range(2, W+2):
    if S[k][j] == '.':
      counter[k][j] = 10**7

counter[Ch][Cw] = 0




now = [start]
now_2 = [start]
while len(now_2) > 0:
  new = []
  for item in now_2:
    x = item[0]
    y = item[1]
    if counter[x+1][y] == 10**7:
      counter[x+1][y] = 0
      new.append((x+1, y))
    if counter[x][y+1] == 10**7:
      counter[x][y+1] = 0
      new.append((x, y+1))
    if counter[x-1][y] == 10**7:
      counter[x-1][y] = 0
      new.append((x-1, y))
    if counter[x][y-1] == 10**7:
      counter[x][y-1] = 0
      new.append((x, y-1))
  now += new
  now_2 = new


if counter[Dh][Dw] == 0:
  print(0)
  exit()
ans = 0
while counter[Dh][Dw] == 10**7:
  if len(now) == 0:
    print(-1)
    exit() 
  nextlist = []
  ans += 1
  for item in now:
    x = item[0]
    y = item[1]
    if counter[x+2][y+2] > ans:
      counter[x+2][y+2] = ans
      nextlist.append((x+2, y+2))
    if counter[x+2][y+1] > ans:
      counter[x+2][y+1] = ans
      nextlist.append((x+2, y+1))
    if counter[x+2][y] > ans:
      counter[x+2][y] = ans
      nextlist.append((x+2, y))
    if counter[x+2][y-1] > ans:
      counter[x+2][y-1] = ans
      nextlist.append((x+2, y-1))
    if counter[x+2][y-2] > ans:
      counter[x+2][y-2] = ans
      nextlist.append((x+2, y-2))
    if counter[x+1][y+2] > ans:
      counter[x+1][y+2] = ans
      nextlist.append((x+1, y+2))
    if counter[x+1][y-2] > ans:
      counter[x+1][y-2] = ans
      nextlist.append((x+1, y-2))
    if counter[x][y+2] > ans:
      counter[x][y+2] = ans
      nextlist.append((x, y+2))
    if counter[x][y-2] > ans:
      counter[x][y-2] = ans
      nextlist.append((x, y-2))
    if counter[x-2][y+2] > ans:
      counter[x-2][y+2] = ans
      nextlist.append((x-2, y+2))
    if counter[x-2][y+1] > ans:
      counter[x-2][y+1] = ans
      nextlist.append((x-2, y+1))
    if counter[x-2][y] > ans:
      counter[x-2][y] = ans
      nextlist.append((x-2, y))
    if counter[x-2][y-1] > ans:
      counter[x-2][y-1] = ans
      nextlist.append((x-2, y-1))
    if counter[x-2][y-2] > ans:
      counter[x-2][y-2] = ans
      nextlist.append((x-2, y-2))
    if counter[x-1][y+2] > ans:
      counter[x-1][y+2] = ans
      nextlist.append((x-1, y+2))
    if counter[x-1][y-2] > ans:
      counter[x-1][y-2] = ans
      nextlist.append((x-1, y-2))
    if counter[x-1][y-1] > ans:
      counter[x-1][y-1] = ans
      nextlist.append((x-1, y-1))
    if counter[x-1][y+1] > ans:
      counter[x-1][y+1] = ans
      nextlist.append((x-1, y+1))
    if counter[x+1][y+1] > ans:
      counter[x+1][y+1] = ans
      nextlist.append((x+1, y+1))
    if counter[x+1][y-1] > ans:
      counter[x+1][y-1] = ans
      nextlist.append((x+1, y-1))
      
  
  now_2 = nextlist
  while len(now_2) > 0:
    new = []
    for item in now_2:
      x = item[0]
      y = item[1]
      if counter[x+1][y] == 10**7:
        counter[x+1][y] = 0
        new.append((x+1, y))
      if counter[x][y+1] == 10**7:
        counter[x][y+1] = 0
        new.append((x, y+1))
      if counter[x-1][y] == 10**7:
        counter[x-1][y] = 0
        new.append((x-1, y))
      if counter[x][y-1] == 10**7:
        counter[x][y-1] = 0
        new.append((x, y-1))
    nextlist += new
    now_2 = new
  now = nextlist
  
  if ans > 10**7:
    print(-1)
    exit()
print(ans)

Solution (Python):
from collections import deque
import sys

def BFS(task, ct):
  D = [(1,0), (0,1), (-1,0), (0,-1)]
  semi_visited = set()
  task_n = deque([])
  for s in task:
    semi_visited.add(s)
  while task:
    s = task.popleft()
    
    if s == (hg, wg):
      print(ct)
      sys.exit()
    x = s[0]
    y = s[1]
    for d in D:
      s_n = (x+d[0], y+d[1])
      
      if 0 <= s_n[0] <= H-1 and 0 <= s_n[1] <= W-1 and (s_n not in semi_visited) and S[s_n[0]][s_n[1]] == ".":
        task.append(s_n)
        semi_visited.add(s_n) 
        visited.add(s_n)
  
  for s in semi_visited:
    warp(s, task_n)
  return (ct+1, task_n)

def warp(p, task_n):
  
  x = p[0]
  y = p[1]
  for dh in range(-2,3):
    for dw in range(-2,3):
      s_n = (x+dh, y+dw)
      if 0 <= s_n[0] <= H-1 and 0 <= s_n[1] <= W-1:
        
        if S[s_n[0]][s_n[1]] == "." and s_n not in visited:
          task_n.append(s_n)
          visited.add(s_n)
  return task_n

H, W = map(int, input().split())
hs, ws = map(int, input().split())
hs -= 1
ws -= 1
hg, wg = map(int, input().split())
hg -= 1
wg -= 1

S = [input() for _ in range(H)]

task = deque([(hs, ws)])
visited = {(hs, ws)}
semi_visited = {(hs, ws)}
ct = 0

while task:
  
  ct, task = BFS(task, ct)
  
  
print(-1)

Solution (Python):
import sys
from collections import deque


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


def main():
    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)]

    q = deque()
    q.append((ch - 1, cw - 1, 0))

    pathA = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    pathB = []
    for i in range(5):
        for j in range(5):
            pathB.append((i - 2, j - 2))
    visited = [[-1] * W for _ in range(H)]

    while q:
        h, w, d = q.popleft()
        if visited[h][w] !=-1:
            continue
        visited[h][w] =d


        for h1, w1 in pathA:
            newh = h + h1
            neww = w + w1
            if newh >= 0 and newh < H and neww >= 0 and neww < W and S[newh][neww] == ".":
                if visited[newh][neww] == -1:
                    q.appendleft((newh, neww, d))

        for h1, w1 in pathB:
            newh = h + h1
            neww = w + w1
            if newh >= 0 and newh < H and neww >= 0 and neww < W and S[newh][neww] == ".":
                q.append((newh, neww, d + 1))

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


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
INF=10**10
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
m=[list(input()) for _ in range(H)]
s=(Ch-1,Cw-1)
g=(Dh-1,Dw-1)
d=[[INF]*W for _ in range(H)]
d[s[0]][s[1]]=0
q=deque()
q.append(s)
while q:
    y,x=q.pop()
    for dy,dx in [(0,1),(1,0),(0,-1),(-1,0)]:
        ny=y+dy
        nx=x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if m[ny][nx]=='.' and d[ny][nx]>d[y][x]:
            q.append((ny,nx))
            d[ny][nx]=d[y][x]
    for dy in range(-2,3):
        for dx in range(-2,3):
            if abs(dy)+abs(dx)<=1:
                continue
            ny=y+dy
            nx=x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if m[ny][nx]=='.' and d[ny][nx]>d[y][x]+1:
                q.appendleft((ny,nx))
                d[ny][nx]=d[y][x]+1
ans=d[g[0]][g[1]]
if ans<INF:
    print(ans)
else:
    print(-1)

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


import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True, fastmath=True, parallel=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] 
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
rows,cols = h,w

OK = "."
NG = "

ss = np.array([[c=="

print(main(ss,ch,cw,dh,dw))

Solution (Python):

from collections import deque
import sys

f_inf = float("inf")



h, w = map(int, input().split())
c_h, c_w = map(int, input().split())
d_h, d_w = map(int, input().split())

grid = []

d = deque()


for i in range(h + 1):
    if i == 0:
        array_tmp = "
    else:
        array_tmp = str(input().strip())
    array_tmp = "
    grid.append(list(array_tmp))


grid[c_h][c_w] = 0

d.append((c_h, c_w))


def check(tar_h, tar_w):
    if tar_h > h or tar_h < 1:
        return -1
    if tar_w > w or tar_w < 1:
        return -1
    if grid[tar_h][tar_w] == ".":
        return f_inf
    if grid[tar_h][tar_w] == "
        return -1
    else:
        return grid[tar_h][tar_w]


while len(d) != 0:
    tar_h, tar_w = d.popleft()
    tar_num = grid[tar_h][tar_w]
    if tar_num == "
        continue

    for i in range(5):
        for j in range(5):
            checknum = check(tar_h + i - 2, tar_w + j - 2)
            if checknum > tar_num:
                if (
                    (i == 2 and j == 1)
                    or (i == 2 and j == 3)
                    or (i == 1 and j == 2)
                    or (i == 3 and j == 2)
                ):
                    grid[tar_h + i - 2][tar_w + j - 2] = tar_num
                    d.appendleft((tar_h + i - 2, tar_w + j - 2))
                    if tar_h == d_h and tar_w == d_w:
                        print("{}".format(tar_num))
                        sys.exit()
                else:
                    if checknum > tar_num + 1:
                        grid[tar_h + i - 2][tar_w + j - 2] = tar_num + 1
                        d.append((tar_h + i - 2, tar_w + j - 2))

if check(d_h, d_w) == f_inf:
    ans = -1
else:
    ans = check(d_h, d_w)

print("{}".format(ans))

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

def main():
    hh,ww = list(map(int,input().split()))
    ch, cw = list(map(int,input().split()))
    dh, dw = list(map(int,input().split()))
    maze=[list(input()) for l in range(hh)]
    segid = 0

    
    for y in range(hh):
        for x in range(ww):
            if maze[y][x]=='.':
                maze[y][x]=math.inf
            elif maze[y][x] == '
                maze[y][x]=int(-1)

    for m in range(hh):
        for n in range(ww):
            if maze[m][n] == math.inf:
                maze[m][n] = segid
                que = deque([[m,n]])
                while que:

                    current_hh, current_ww = que.popleft()
                    for i, j in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                        next_hh, next_ww = current_hh + i, current_ww + j
                        if (next_hh >= 0) and (next_ww >= 0) and (next_hh < hh) and (next_ww < ww):
                            dist = maze[next_hh][next_ww]
                            if dist == math.inf:
                                maze[next_hh][next_ww] = segid
                                que.append([next_hh, next_ww])
                segid += 1



    flag_segid = [1]*segid
    graph = [[] for _ in range(segid)]
    for m in range(hh):
        for n in range(ww):
            current_segid = maze[m][n]
            if (current_segid >= 0 ) and (flag_segid[current_segid] == 1):
                que = deque([[m, n]])
                while que:

                    current_hh, current_ww = que.popleft()
                    for i in [-2, -1, 0, 1, 2]:
                        for j in [-2, -1, 0, 1, 2]:
                            
                            if (i == 0 and j == 0):
                                continue
                            next_hh, next_ww = current_hh + i, current_ww + j
                            if (next_hh >= 0) and (next_ww >= 0) and (next_hh < hh) and (next_ww < ww):
                                next_segid = maze[next_hh][next_ww]
                                if (next_segid != -1) and (next_segid != current_segid):
                                    if not (next_segid in graph[current_segid]):
                                        graph[current_segid].append(next_segid)

                







    start_graph = maze[ch-1][cw-1]
    end_graph = maze[dh-1][dw-1]





    qq = deque()
    cost = [math.inf] * segid
    cost[start_graph] = 0
    qq.append(start_graph)
    while qq:
        v = qq.popleft()
        for i in graph[v]:
            newcost = cost[v] + 1
            if cost[i] > newcost:
                cost[i] = newcost
                qq.append(i)

    if cost[end_graph] == math.inf:
        print(-1)
    else:
        print(cost[end_graph])

main()

Solution (Python):
from collections import deque
 
h,w=map(int,input().split())
ch,cw=map(int,input().split())
ddh,ddw=map(int,input().split())
s=[[c for c in input()] for _ in range(h)]

q=deque([(ch-1,cw-1,0)])
visit=[[0]*w for _ in range(h)]

while len(q)>0:
    uh,uw,cnt=deque.popleft(q)
    if visit[uh][uw]==1:
        continue

    stack=[(uh,uw)]
    stack2=[(uh,uw)]
    while len(stack)>0:
        vh,vw=stack.pop()

        visit[vh][vw]=1

        if vh==ddh-1 and vw==ddw-1:
            print(cnt)
            exit(0)

        for dh,dw in ((0,1),(0,-1),(1,0),(-1,0)):
            nh=vh+dh
            nw=vw+dw
            if 0<=nh<h and 0<=nw<w and visit[nh][nw]==0 and s[nh][nw]=='.':
                stack.append((nh,nw))
                stack2.append((nh,nw))

    
    while len(stack2)>0:
        vh,vw=stack2.pop()

        for dh in range(-2,3):
            for dw in range(-2,3):
                nh=vh+dh
                nw=vw+dw

                if 0<=nh<h and 0<=nw<w and visit[nh][nw]==0 and s[nh][nw]=='.':
                    deque.append(q,(nh,nw,cnt+1))
                
print(-1)

Solution (Python):
from sys import stdin
from collections import deque, defaultdict

readline = stdin.readline

def main():
    H, W = map(int, readline().rstrip().split())
    CH, CW = map(lambda x: int(x) - 1, readline().rstrip().split())
    DH, DW = map(lambda x: int(x) - 1, readline().rstrip().split())
    S = [readline().rstrip() for _ in range(H)]
    v = defaultdict(lambda : False)
    dq = deque([(0, CH, CW)])
    while dq:
        d, h, w = dq.popleft()
        
        if (h, w) == (DH, DW):
            print(d)
            exit()
        if v[(h, w)]:
            continue
        v[(h, w)] = True
        for mh, mw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nh = mh + h
            nw = mw + w
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[(nh, nw)]:
                dq.appendleft([d, nh, nw])
        for mh in range(-2, 3):
            for mw in range(-2, 3):
                if mh == mw == 0:
                    continue
                nh = mh + h
                nw = mw + w
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[(nh, nw)]:
                    dq.append([d + 1, nh, nw])
    print(-1)

if __name__ == "__main__":
    main()

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

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().rstrip() for _ in range(H)]
v = [[False] * W for _ in range(H)]
dq = deque([(0, CH, CW)])
while dq:
    d, h, w = dq.popleft()
    if (h, w) == (DH, DW):
        print(d)
        exit()
    if v[h][w]:
        continue
    v[h][w] = True
    for mh, mw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nh, nw = mh + h, mw + w
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
            dq.appendleft([d, nh, nw])
    for mh in range(-2, 3):
        for mw in range(-2, 3):
            if mh == mw == 0:
                continue
            nh, nw = mh + h, mw + w
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[nh][nw]:
                dq.append([d + 1, nh, nw])
print(-1)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch, cw, dh, dw = ch - 1, cw - 1, dh - 1, dw - 1
s = [list(input()) for i in range(h)]
d = [[-1] * w for i in range(h)]
Q = deque([(ch, cw, 0)])
while Q:
    x, y, broken = Q.popleft()
    if d[x][y] != -1:
        continue
    d[x][y] = broken
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if 0 <= x + dx < h and 0 <= y + dy < w and s[x + dx][y + dy] == "." and d[x + dx][y + dy] == -1:
                if abs(dx) + abs(dy) == 1:
                    Q.appendleft((x + dx, y + dy, broken))
                else:
                    Q.append((x + dx, y + dy, broken + 1))
print(d[dh][dw])

Solution (Python):
"""
    Satwik_Tiwari ;) .
    21st AUGUST , 2020  - FRIDAY
"""



from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter  
from itertools import combinations as comb 
from itertools import permutations as permutate
from bisect import bisect_left as bl


from bisect import bisect_right as br
from bisect import bisect





BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)





from types import GeneratorType
def iterative(f, stack=[]):
  def wrapped_func(*args, **kwargs):
    if stack: return f(*args, **kwargs)
    to = f(*args, **kwargs)
    while True:
      if type(to) is GeneratorType:
        stack.append(to)
        to = next(to)
        continue
      stack.pop()
      if not stack: break
      to = stack[-1].send(to)
    return to
  return wrapped_func





mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") 
def out(var): sys.stdout.write(str(var))  
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())

def zerolist(n): return [0]*n
def nextline(): out("\n")  
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def google(p):
    print('Case 
def lcm(a,b): return (a*b)//gcd(a,b)
def power(x, y, p) :
    res = 1     
    x = x % p  
    if (x == 0) :
        return 0
    while (y > 0) :
        if ((y & 1) == 1) : 
            res = (res * x) % p

        y = y >> 1      
        x = (x * x) % p
    return res
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True



def djkistra(g,st,dist): 
    pq = []
    dist[st] = 0
    heappush(pq,(0,st))
    while(len(pq) != 0):
        curr = heappop(pq)[1]
        for i in range(0,len(g[curr])):
            b = g[curr][i][0]
            w = g[curr][i][1]
            if(dist[b] > dist[curr] + w):
                dist[b] = dist[curr]+w
                heappush(pq,(dist[b],b))

def solve():
    n,m = sep()
    x,y = sep()
    xnot ,ynot = sep()
    x-=1
    y-=1
    xnot-=1
    ynot-=1

    grid = []
    for i in range(n):
        temp = list(inp())
        grid.append(temp)

    g = [[] for i in range(n*m)]

    for i in range(n):
        for j in range(m):
            if(grid[i][j] == '
                continue
            for ii in range(i-2,i+3):
                for jj in range(j-2,j+3):
                    if(ii==i and jj==j):
                        continue
                    if(0<=ii<n and 0<=jj<m and grid[ii][jj] == '.'):
                        if(abs(ii-i)+abs(jj-j) == 1):
                            g[i*m+j].append((ii*m+jj,0))
                        else:
                            g[i*m+j].append((ii*m+jj,1))
                        
    
    

    dist = [10**9]*(n*m)
    
    djkistra(g,x*m+y,dist)
    
    
    if(dist[xnot*m+ynot] == 10**9):
        print(-1)
    else:
        print(dist[xnot*m+ynot])









testcase(1)

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

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().rstrip() for _ in range(H)]
visited = [[False] * W for _ in range(H)]
dq = deque([(0, Ch, Cw)])
while dq:
    d, i, j = dq.popleft()
    if (i, j) == (Dh, Dw):
        print(d)
        exit()
    if visited[i][j]:
        continue
    visited[i][j] = True
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
            dq.appendleft((d, ni, nj))
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.' and not visited[ni][nj]:
                dq.append((d + 1, ni, nj))
print(-1)

Solution (Python):
from numba import njit, b1, i4, i8, f8
import numpy as np
import numba
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    h,w = ss.shape
    inf = 1<<30
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] 
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if (xx if xx>=0 else -xx)+(yy if yy>=0 else -yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
      

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
rows,cols = h,w

OK = "."
NG = "

ss = np.array([[c=="

print(main(ss,ch,cw,dh,dw))