Problem:
 Score : 400 points    Problem Statement A maze is composed of a grid of H \times W squares - H vertical, W horizontal.  The square at the i -th row from the top and the j -th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is . .  There is a magician in (C_h,C_w) . He can do the following two kinds of moves:   Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.  Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.   In either case, he cannot go out of the maze.  At least how many times does he need to use the magic to reach (D_h, D_w) ?      Constraints  1 \leq H,W \leq 10^3  1 \leq C_h,D_h \leq H  1 \leq C_w,D_w \leq W  S_{ij} is # or . .  S_{C_h C_w} and S_{D_h D_w} are . .  (C_h,C_w) \neq (D_h,D_w)         Input Input is given from Standard Input in the following format:  H  W  C_h  C_w  D_h  D_w  S_{11}\ldots S_{1W}  \vdots  S_{H1}\ldots S_{HW}       Output Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w) , print -1 instead.        Sample Input 1 4 4
1 1
4 4
..#.
..#.
.#..
.#..      Sample Output 1 1  For example, by walking to (2,2) and then using the magic to travel to (4,4) , just one use of magic is enough.  Note that he cannot walk diagonally.       Sample Input 2 4 4
1 4
4 1
.##.
####
####
.##.      Sample Output 2 -1  He cannot move from there.       Sample Input 3 4 4
2 2
3 3
....
....
....
....      Sample Output 3 0  No use of magic is needed.       Sample Input 4 4 5
1 2
2 5
#.###
####.
#..##
#..##      Sample Output 4 2

Solution (Python):
import sys
from collections import deque


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


def main():
    INF = 10**7
    h, w = [int(i) for i in input().split()]
    c_h, c_w = [int(i) for i in input().split()]
    d_h, d_w = [int(i) for i in input().split()]
    grid = [["
    for _ in range(h):
        line = ["
        grid.append(line)
    grid.append(["
    warp_count = [[INF] * (w + 2) for _ in range(h + 2)]
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    warps = []
    for x in range(-2, 3):
        for y in range(-2, 3):
            if x == 0 and y == 0:
                continue
            if (x, y) not in directions:
                warps.append((x, y))

    stack = deque()
    warp_count[c_h][c_w] = 0
    stack.append((c_h, c_w, 0))

    while stack:
        _h, _w, warp = stack.pop()
        if warp > warp_count[_h][_w]:
            continue
        warp_count[_h][_w] = warp

        
        for _a, _b in directions:
            if grid[_h + _a][_w + _b] != "
                stack.append((_h + _a, _w + _b, warp))

        
        for x, y in warps:
            if _h + x < 0 or _h + x > h or _w + y < 0 or _w + y > w:
                continue
            elif grid[_h + x][_w + y] == "
                continue
            if warp_count[_h + x][_w + y] > warp + 1:
                stack.appendleft((_h + x, _w + y, warp + 1))

    if warp_count[d_h][d_w] == INF:
        print(-1)
    else:
        print(warp_count[d_h][d_w])
    return


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
H,W=map(int, input().split())
Ch, Cw=map(int, input().split())
Dh, Dw=map(int, input().split())
maze=[]
for _ in range(H):
    RRR=(input().replace(".","0")).replace("
    maze.append(list(map(int, RRR)))

dis=[[H**2*W**2 for _ in range(W+1)]for _ in range(H+1)]
Es=[[H**2*W**2 for _ in range(W+1)]for _ in range(H+1)]
start=(Ch,Cw,0)
goal=(Dh,Dw)
walk=[(1,0),(-1,0),(0,1),(0,-1)]
wap=[]
for i in range(-2,3):
    for j in range(-2,3):
        wap.append((i,j))
wap.remove((0,0))
for each in walk:
    wap.remove(each)
cand=[start]
dis[start[0]][start[1]]=0
flag=False
edge=[]
while len(cand)>0:
    
    place=cand.pop()
    hh,ww,cost=place
    if hh==Dh and ww==Dw:
        flag=True
    for each in walk:
        h1,w1=hh+each[0],ww+each[1]
        if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost:
            dis[h1][w1]=cost
            cand.append((h1,w1,cost))
        elif h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==1 and Es[hh][ww]>cost:
            Es[hh][ww]=cost
            edge.append((hh,ww,cost))
            
    if len(cand)==0:
        for place in edge:
            hh,ww,cost=place
            for each in wap:
                h1,w1=hh+each[0],ww+each[1]
                
                if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost+1:
                    dis[h1][w1]=cost+1
                    cand.append((h1,w1,cost+1))
        edge=[]
        
if flag:
    print(dis[Dh][Dw])
else:
    print(-1)

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

sys.setrecursionlimit(10**7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())

INF = 10**7


def main():
    H, W = in_nn()
    Ch, Cw = in_nn()
    Dh, Dw = in_nn()
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    grid = in_map2(H)

    dp = [[INF for _ in range(W)] for _ in range(H)]
    dp[Ch][Cw] = 0

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

    while q:
        now = q.popleft()
        x, y = now
        for px in range(-2, 3):
            for py in range(-2, 3):
                if (px == 0 and py == 0):
                    continue
                nx, ny = x + px, y + py
                if 0 <= nx < W and 0 <= ny < H and grid[ny][nx]:
                    if (px == -1 and py == 0) or (px == 1 and py == 0) \
                            or (px == 0 and py == -1) or (px == 0 and py == 1):
                        if dp[ny][nx] > dp[y][x]:
                            dp[ny][nx] = dp[y][x]
                            q.appendleft((nx, ny))
                    else:
                        if dp[ny][nx] > dp[y][x] + 1:
                            dp[ny][nx] = dp[y][x] + 1
                            q.append((nx, ny))

    
    

    if dp[Dh][Dw] >= INF:
        ans = -1
    else:
        ans = dp[Dh][Dw]

    print(ans)


if __name__ == '__main__':
    main()

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 -= 1
cw -= 1
dh -= 1
dw -= 1
vec5 = []
vec = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(-2, 3):
    for j in range(-2, 3):
        if abs(i) + abs(j) < 2:
            continue
        vec5 += [(i,j)]

c = 0
q = [(ch, cw)]
while len(q) > 0:
    nq = []
    while len(q) > 0:
        i, j = q.pop()
        s[i][j] = c
        nq += [(i,j)]
        for v in vec:
            ii = i + v[0]
            jj = j + v[1]
            if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
                q += [(ii, jj)]


    while len(nq) > 0:
        i, j = nq.pop()
        for v in vec5:
            ii = i+v[0]
            jj = j+v[1]
            if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
                q += [(ii, jj)]
    c += 1
if s[dh][dw] == '.':
    print(-1)
else:
    print(s[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):
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] 
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
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())
S = ['
for i in range(H):
    S.append('
S.append('
S.append('

CH += 2
CW += 2
DH += 2
DW += 2

dist = [[-1 for i in range(W + 4)] for j in range(H + 4)]
dist[CH - 1][CW - 1] = 0
q = deque()
q.append([CH, CW])

while len(q) != 0:
    current_pos = q.popleft()
    y = current_pos[0]
    x = current_pos[1]
    if (y, x) == (DH, DW):
        print(dist[DH - 1][DW - 1])
        exit()

    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == j == 0:
                continue
            next_y = y + i
            next_x = x + j

            if S[next_y - 1][next_x - 1] == '
                continue
            if dist[next_y - 1][next_x - 1] == dist[y - 1][x - 1]:
                continue

            if dist[next_y - 1][next_x - 1] == -1 or dist[next_y - 1][next_x - 1] > dist[y - 1][x - 1]:
                if (i == 0 and j in (-1, 1)) or (j == 0 and i in (-1, 1)):
                    q.appendleft([next_y, next_x])
                    dist[next_y - 1][next_x - 1] = dist[y - 1][x - 1]
                else:
                    if dist[next_y - 1][next_x - 1] == -1:
                        q.append([next_y, next_x])
                        dist[next_y - 1][next_x - 1] = dist[y - 1][x - 1] + 1

print(-1)

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

h,w = map(int,input().rstrip().split())
sy,sx = map(int,input().rstrip().split())
gy,gx = map(int,input().rstrip().split())
a = [list(input().rstrip())for _ in range(h)]

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

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

def bfs():
    d = [[float("inf")]*w for _ in range(h)]
    q = deque([])
    q.append((sx,sy))
    d[sy][sx] = 0 
    goal = False
    local_area = deque([])

    while q:
        p = q.popleft()
        local_area.append((p[0],p[1]))
        if p[0] == gx and p[1] == gy:
            goal = True
            break

        for i in range(4):
            nx = p[0]+dx[i]
            ny = p[1]+dy[i]
            if 0<=nx<w and 0<=ny<h and a[ny][nx] != "
                q.append((nx,ny))
                d[ny][nx] = d[p[1]][p[0]]
        if len(q) == 0 and goal == False:
            while local_area:
                p = local_area.popleft()
                for i in range(-2,3):
                    for j in range(-2,3):
                        nx = p[0]+i 
                        ny = p[1]+j
                        if 0<=nx<w and 0<=ny<h and a[ny][nx] != "
                            q.append((nx,ny))
                            d[ny][nx] = d[p[1]][p[0]] + 1                        

    if goal == False:
        return -1
    else:
        return d[gy][gx]
        
print(bfs())

Solution (Python):
from collections import deque
H, W = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())
s = [input() for _ in range(H)]

res = [[10**8 for _ in range(W)] for _ in range(H)]
res[ch-1][cw-1] = 0
deq = deque([(ch-1, cw-1)])

DH = [1, 0, -1, 0]
DW = [0, 1, 0, -1]

def inc(h, w):
	if 0 <= h < H and 0 <= w < W:
		return True
	else:
		return False

while deq:
	h, w = deq.pop()
	for dh, dw in zip(DH, DW):
		if inc(h+dh, w+dw) == False or s[h+dh][w+dw] == "
			continue
		if res[h+dh][w+dw] > res[h][w]:
			res[h+dh][w+dw] = res[h][w]
			deq.append((h+dh, w+dw))
	for dh in range(-2, 3):
		for dw in range(-2, 3):
			if inc(h+dh, w+dw) == False or s[h+dh][w+dw] == "
				continue
			if res[h+dh][w+dw] > res[h][w]+1:
				res[h+dh][w+dw] = res[h][w]+1
				deq.appendleft((h+dh, w+dw))

if res[gh-1][gw-1] > 10**7:
	print(-1)
else:
	print(res[gh-1][gw-1])

Solution (Python):
h, w = map(int,input().split())
sx, sy = map(int,input().split())
gx, gy = map(int,input().split())
S = [input() for i in range(h)]

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

A = [(-1,0),(1,0),(0,-1),(0,1)]
B = []
for i in range(-2,3):
    for j in range(-2,3):
        if i!= 0 or j!=0:
            B.append((i,j))





M = [[] for i in range(h*w)]

for i in range(h):
    for j in range(w):
        if S[i][j] == ".":
            for a in A:
                ai = i+a[0]
                aj = j+a[1]
                if 0 <= ai < h and 0 <= aj < w and S[ai][aj] == ".":
                    M[i*w+j].append((ai*w+aj, 0))
            for b in B:
                bi = i+b[0]
                bj = j+b[1]
                if 0 <= bi < h and 0 <= bj < w and S[bi][bj] == ".":
                    M[i*w+j].append((bi*w+bj,1))







n = h*w

import heapq

big = 10**9
D = [big] * n  
P = [-1] * n  
D[sx*w+sy] = 0
V = [0] * n  
Q = []  


heapq.heappush(Q, (0, sx*w+sy))


while len(Q) > 0:
    
    q = heapq.heappop(Q)
    u = q[1]
    du = q[0]
    if V[u] == 0:
        V[u] = 1
        
        for i in range(len(M[u])):
            v = M[u][i][0]
            luv = M[u][i][1]
            
            if V[v] == 0:
                alt = du + luv
                if D[v] > alt:
                    D[v] = alt
                    P[v] = u
                    heapq.heappush(Q, (alt, v))
                    
                    

ans = D[gx*w+gy]
if ans > 10**7:
    ans = -1
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]*((H-1)*W + W)  

    def bfs_2d(sy, sx, v):
        que = deque()
        V[sy*W+sx] = v
        que.append(sy*W+sx)
        d = ((0, -1), (0, 1), (-1, 0), (1, 0))
        while que:
            u = que.popleft()
            uh, uw = u//W, u % 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*W+next_w] != -1:
                    continue
                if A[next_h][next_w] == '
                    continue
                V[next_h*W+next_w] = v
                que.append(next_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+w] == V[(h+dh)*W + w+dw]:
                        continue
                    if V[(h+dh)*W + w+dw] in used[V[h*W+w]]:
                        continue
                    G[V[h*W+w]].append(V[(h+dh)*W + w+dw])
                    used[V[h*W+w]].add(V[(h+dh)*W + w+dw])

    
    
    

    def bfs(s, g, N):
        que = deque([s])
        dist = [-1]*N
        dist[s] = 0
        while que:
            v = que.popleft()
            for i in G[v]:
                if dist[i] != -1:
                    continue
                que.append(i)
                dist[i] = dist[v] + 1
        return dist[g]

    s = V[Ch*W+Cw]
    g = V[Dh*W+Dw]
    ans = bfs(s, g, vertex)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    H,W = LMIIS()
    Ch,Cw = LMIIS()
    Ch -= 1
    Cw -= 1
    Dh,Dw = LMIIS()
    Dh -= 1
    Dw -= 1
    S = []
    for i in range(H):
        S.append(input())
    
    num_warp = []
    for i in range(H):
        num_warp.append([-1]*W)
    
    targets = deque([(Ch,Cw,0)])


    def check_and_move(y,x,d):
        if 0 <= y < H and 0 <= x < W and num_warp[y][x] == -1 and S[y][x] == '.':
            num_warp[y][x] = d
            return True
        return False




    
    while targets:
        y,x,d = targets.pop()
        if not check_and_move(y,x,d):
            continue

        for y2,x2 in [(y-1,x),(y,x+1),(y+1,x),(y,x-1)]:
            targets.append((y2,x2,d))

        for y2,x2 in[
                (y-2,x-2),(y-2,x-1),(y-2,x),(y-2,x+1),(y-2,x+2),
                (y-1,x-2),(y-1,x-1),(y-1,x+1),(y-2,x+2),
                (y,x-2),(y,x+2),
                (y+1,x-2),(y+1,x-1),(y+1,x+1),(y+1,x+2),
                (y+2,x-2),(y+2,x-1),(y+2,x),(y+2,x+1),(y+2,x+2)
            ]:
            targets.appendleft((y2,x2,d+1))

    print(num_warp[Dh][Dw])



    
main()

Solution (Python):
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1,ls=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'
    
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase

read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()













class Bit: 
    def __init__(self,n,init=None):
        self.size=n
        self.m=len(bin(self.size))-2
        self.arr=[0]*(2**self.m+1)
        self.el=[0]*(2**self.m+1)
        if init!=None:
            for i in range(len(init)):
                self.add(i,init[i])
                self.el[i]=init[i]

    def __str__(self):
        a=[self.sum(i+1)-self.sum(i) for i in range(self.size)]
        return str(a)
        
    def add(self,i,x):
        if not 0<i<=self.size:return NotImplemented
        self.el[i]+=x
        while i<=self.size:
            self.arr[i]+=x
            i+=i&(-i)
        return
    
    def sum(self,i):
        if not 0<=i<=self.size:return NotImplemented
        rt=0
        while i>0:
            rt+=self.arr[i]
            i-=i&(-i)
        return rt
    
    def __getitem__(self,key):
        return self.el[key]
        return self.sum(key+1)-self.sum(key)

    def __setitem__(self,key,value):
        self.add(key,value-self.sum(key+1)+self.sum(key))

    def l_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<=self.size and self.arr[x+k]<w:
                w-=self.arr[x+k]
                x+=k
            k>>=1
        return x+1
        
    def u_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<=self.size and self.arr[x+k]<=w:
                w-=self.arr[x+k]
                x+=k
            k>>=1
        return x+1
        
class Bit0(Bit): 
    def add(self,j,x):
        super().add(j+1,x)
    def l_bound(self,w):
        return max(super().l_bound(w)-1,0)
    def u_bound(self,w):
        return max(super().u_bound(w)-1,0)

class Multiset(Bit0):
    def __init__(self,max_v):
        super().__init__(max_v)
    def insert(self,x):
        super().add(x,1)
    def find(self,x):
        return super().l_bound(super().sum(x))
    def __str__(self):
        return str(self.arr)

def compress(L):
    dc={v:i for i,v in enumerate(sorted(set(L)))}
    return [dc[i] for i in L]


show_flg=False
show_flg=True

ans=0

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

w+=2
m=[1]*w
for i in range(h):
    s=input()
    m+=[1]+[i=='
m+=[1]*w
h+=2
n=h*w
v=[-1]*w*h

dc=dict()
cn=0
def bfs(x):
    global cn
    q=[x]
    v[x]=x
    dc[x]=cn
    cn+=1
    while q:
        c=q.pop()
        for nx in [c+1,c-1,c+w,c-w]:
            if 0<=nx<n and m[nx]!=1 and v[nx]==-1:
                q+=nx,
                v[nx]=x
    return        
            
for i in range(n):
    if m[i]!=1 and v[i]==-1:
        bfs(i)

g=[set()for i in range(cn)]
nb=[-2*w+1,-2*w+2,-w+1,-w+2,1,2,2*w+1,2*w+2,w+1,w+2,+w,+2*w,-w,-2*w,-2*w-1,-2*w-2,-w-1,-w-2,-1,-2,2*w-1,2*w-2,w-1,w-2]

for i in range(n):
    if m[i]==1:
        continue
    for di in nb:
        nx=i+di
        if 0<=nx<n and m[nx]!=1 and dc[v[i]]!=dc[v[nx]]:
            g[dc[v[i]]].add(dc[v[nx]])
            g[dc[v[nx]]].add(dc[v[i]])

q=deque([dc[v[sh*w+sw]]])
dist=[-1]*cn
dist[dc[v[sh*w+sw]]]=0
while q:
    c=q.pop()
    for nx in g[c]:
        if dist[nx]==-1:
            q.appendleft(nx)
            dist[nx]=dist[c]+1

print(dist[dc[v[gh*w+gw]]])

Solution (Python):
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 = [list(input()) for _ in range(h)]

from collections import deque

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

ans = -1
while q:
    i, j, wc = q.popleft()
    if i == dh and j == dw:
        ans = wc
        break
    for mi, mj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        ni, nj = i + mi, j + mj
        if 0 <= nj < w and 0 <= ni < h:
            if S[ni][nj] == '.' and visited[ni][nj] != wc:
                visited[ni][nj] = wc
                q.appendleft([ni, nj, wc])

    for wi, wj 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)):
        ni, nj = i+wi, j+wj
        if (0 <= nj < w and 0 <= ni < h and S[ni][nj] == '.' and
            visited[ni][nj] == -1):
            visited[ni][nj] = wc+1
            q.append([ni, nj, wc+1])
print(ans)

Solution (Python):
from collections import deque
import sys

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
S = [input() for _ in range(H)]

cost = [[0] * W for _ in range(H)]


dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
que = deque([(ch-1, cw-1, 0)])
used = {(ch-1, cw-1)}
warp = [(ch-1, cw-1, 0)]
ddd = []
for i in range(-2,3):
    for j in range(-2,3):
        if (i,j) in dd or i == j == 0:
            continue
        ddd.append((i,j))    

idx = 0
while que:
    while que:
        s, t, cost = que.popleft()
        if s == dh-1 and t == dw-1: 
            print(cost)
            sys.exit()
            break
        for di, dj in dd:
            xi = s + di; yj = t + dj
            if (not 0 <= xi < H) or (not 0 <= yj < W) or S[xi][yj] == '
                continue
            used.add((xi, yj))
            que.append((xi, yj, cost))
            warp.append((xi,yj, cost)) 
            
    while idx <= len(warp) - 1:
        s, t, cost = warp[idx]
        for di, dj in ddd:
            xi = s + di; yj = t + dj
            if (not 0 <= xi < H) or (not 0 <= yj < W) or S[xi][yj] == '
                continue
            used.add((xi, yj))
            que.append((xi, yj, cost+1))
            warp.append((xi,yj, cost+1))
        idx += 1
        if que:
            break

print(-1)

Solution (Python):


import sys
import math
import time

import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools

def bfs(sx, sy):
  que = deque([[sy,sx]])
  D =  [(0,1), (1,0), (0,-1), (-1,0)]

  DD =  [(-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 que:
    y,x = que.popleft()
    flag = 0
    for i,j in D:
      if(x+i<0 or y+j<0 or x+i>W-1 or y+j>H-1):
        continue
      dist = G[y+j][x+i]
      if(G[y+j][x+i] != "
        if(type(G[y+j][x+i]) is str):
          G[y+j][x+i] = G[y][x]
          que.appendleft([y+j,x+i])
        elif(dist>G[y][x]):
          G[y+j][x+i] = G[y][x]
          que.appendleft([y+j,x+i])
      else:
        flag = 1
      if(flag == 1):
          flag = 0
          for k,l in DD:
              if(x+k<0 or y+l<0 or x+k>W-1 or y+l>H-1):
                  continue
              dist = G[y+l][x+k]
              
              if(G[y+l][x+k] != "
                  if(type(G[y+l][x+k]) is str):
                      G[y+l][x+k] = G[y][x]+1
                      que.append([y+l,x+k])
                  elif(dist>G[y][x]+1):
                      G[y+l][x+k] = G[y][x]+1
                      que.append([y+l,x+k])

sys.setrecursionlimit(10**7)






H, W = map(int, input().split())
magicY, magicX = map(int, input().split())
goalY, goalX = map(int, input().split())
G = [list(input()) for i in range(H)]
G[magicY-1][magicX-1] = 0
ans = 0



bfs(magicX-1, magicY-1)

if(G[goalY-1][goalX-1]=="."):
    print(-1)
else:
    print(G[goalY-1][goalX-1])