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

Solution (Python):
from collections import deque
import sys


mX = [0, 1, 0, -1]
mY = [1, 0, -1, 0]
zX = [2, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, -1, -1, -1, -1, -2, -2, -2, -2, -2]
zY = [2, 1, 0, -1, -2, 2, 1, -1, -2, 2, -2, 2, -2, 1, -1, 2, 1, 0, -1, -2]


def bfs(u, S, M, H, W):  

    q = deque()
    q.append(u)
    visited = deque()
    while q:
        while q:
            u = q.popleft()
            visited.append([u[0], u[1]])

            
            for i in range(4):
                nx, ny = u[0] + mX[i], u[1] + mY[i]

                if nx < 0 or H <= nx or ny < 0 or W <= ny or S[nx][ny] == "
                    continue

                if M[nx][ny] == -1 or M[nx][ny] > M[u[0]][u[1]]:  
                    M[nx][ny] = M[u[0]][u[1]]  
                    q.append([nx, ny])
                    visited.append([nx, ny])



        
        while visited:
            u = visited.popleft()
            for j in range(20):
                wx = u[0] + zX[j]
                wy = u[1] + zY[j]
                if wx < 0 or H <= wx or wy < 0 or W <= wy or S[wx][wy] == "
                    continue
                if M[wx][wy] == -1 or M[wx][wy] > M[u[0]][u[1]] + 1:  
                    M[wx][wy] = M[u[0]][u[1]] + 1
                    q.append([wx, wy])


def main():

    H, W = map(int, sys.stdin.readline().rstrip().split())
    Ch, Cw = map(int, sys.stdin.readline().rstrip().split())
    Dh, Dw = map(int, sys.stdin.readline().rstrip().split())

    S = []
    for i in range(H):
        S.append(sys.stdin.readline().rstrip())

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

    if S[Ch - 1][Cw - 1] == "
        print(-1)
        return

    M[Ch - 1][Cw - 1] = 0
    bfs([Ch - 1, Cw - 1], S, M, H, W)

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


main()

Solution (Python):
from heapq import heappush, heappop
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() for _ in range(h)]

INF = 10**10
cost = [[INF] * w for _ in range(h)]

dxy = [(0, +1, 0), (0, 0, +1), (0, -1, 0), (0, 0, -1)]
dxy += [(1, i, j) for i in [-2, 2] for j in range(-2, 3)]
dxy += [(1, i, j) for j in [-2, 2] for i in range(-1, 2)]
dxy += [(1, -1, -1), (1, -1, +1), (1, +1, -1), (1, +1, +1)]

q = [(0, ch, cw)]
cost[ch][cw] = 0
while q:
    c, x, y = heappop(q)
    if cost[x][y] < c:
        continue

    if x == dh and y == dw:
        break

    for c_, dx_, dy_ in dxy:
        nx = x + dx_
        ny = y + dy_
        nc = c + c_
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if s[nx][ny] == '
            continue
        if cost[nx][ny] <= nc:
            continue
        cost[nx][ny] = nc
        heappush(q, (nc, nx, ny))

ans = -1 if cost[dh][dw] == INF else cost[dh][dw]
print(ans)

Solution (Python):
h,w = map(int, input().split())
ch, cw = map(int, input().split())
ch -= 1
cw -= 1
dh,dw = map(int, input().split())
dh -= 1
dw -= 1

def trans(s):
    res = []
    for i in s:
        if i == '.':
            res.append(-1)
        else:
            res.append(-2)
    return res

def move(x,y,dq,dq_next):
    for ix,iy in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
        if ix > h-1 or ix < 0 or iy > w-1 or iy < 0:
            continue
        if (m[ix][iy] == -1) or (m[ix][iy] > m[x][y]):
            m[ix][iy] = m[x][y]
            dq.append((ix, iy))
    for ix, iy in [(x-2, y-2), (x-2, y-1), (x-2, y), (x-2, y+1), (x-2, y+2),
                        (x-1, y-2), (x-1, y-1), (x-1, y+1), (x-1, y+2),
                        (x, y-2), (x, y+2),
                        (x+1, y-2), (x+1, y-1), (x+1, y+1), (x+1, y+2),
                        (x+2, y-2), (x+2, y-1), (x+2, y), (x+2, y+1), (x+2, y+2)]:
        if ix > h-1 or ix < 0 or iy > w-1 or iy < 0:
            continue
        if m[ix][iy] == -1:
            m[ix][iy] = m[x][y] + 1
            dq_next.append((ix, iy))
            
m = [trans(input()) for _ in range(h)]

from collections import deque

m[ch][cw] = 0

def main():
    dq = deque()
    dq_next = deque()
    dq.append((ch,cw))
    s_moved = set()
    while True:
        while len(dq)>0:
            xx, yy = dq.popleft()
            if not (xx, yy) in s_moved:
              if xx == dh and yy == dw:
                  return m[xx][yy]
              move(xx, yy, dq, dq_next)
              s_moved.add((xx, yy))
        if len(dq_next) > 0:
            dq = dq_next.copy()
            dq_next = deque()
        else:
            return -1
          
print(main())

Solution (Python):
from collections import deque


def main():

    def f(hi, wi):
        return hi * w + wi

    h, w = map(int, input().split())
    sh, sw = map(int, input().split())
    gh, gw = map(int, input().split())

    s = [input() for _ in range(h)]
    INF = 10 ** 9

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

    dq = deque([f(sh, sw)])
    dist = [[INF] * w for _ in range(h)]
    dist[sh][sw] = 0

    while dq:
        i = dq.popleft()
        hi, wi = divmod(i, w)

        for dh in range(-2, 3):
            for dw in range(-2, 3):
                nh = hi + dh
                nw = wi + dw
                if 0 <= nh <= h - 1 and 0 <= nw <= w - 1 and s[nh][nw] == ".":
                    if abs(dh) + abs(dw) == 1:
                        if dist[hi][wi] < dist[nh][nw]:
                            dist[nh][nw] = dist[hi][wi]
                            dq.appendleft(f(nh, nw))
                    else:
                        if dist[hi][wi] + 1 < dist[nh][nw]:
                            dist[nh][nw] = dist[hi][wi] + 1
                            dq.append(f(nh, nw))

    ans = dist[gh][gw]
    if ans == INF:
        ans = -1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
from collections import deque
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(H, W, Ch, Cw, Dh, Dw, walkable):
    N = HEIGHT * WIDTH
    visited = [0] * N

    start = (Ch + 1) * WIDTH + (Cw + 1)
    goal = (Dh + 1) * WIDTH + (Dw + 1)
    toVisit = []
    toVisit.append(start)

    currentDistance = 0
    while True:
        nextJumpOrigin = []
        while toVisit:
            p = toVisit.pop()
            if p == goal:
                return currentDistance
            if visited[p]:
                continue

            visited[p] = 1
            nextJumpOrigin.append(p)
            for d in [-1, +1, -WIDTH, +WIDTH]:
                if walkable[p + d] and not visited[p + d]:
                    toVisit.append(p + d)

        
        for origin in nextJumpOrigin:
            for dx in [-2, -1, 0, +1, +2]:
                for dy in [-WIDTH * 2, -WIDTH, 0, WIDTH, WIDTH * 2]:
                    p = origin + dx + dy
                    if not walkable[p]:
                        continue
                    if visited[p]:
                        continue
                    toVisit.append(p)

        currentDistance += 1
        if not toVisit:
            return -1


def readMap(H, W):
    global SENTINEL, HEIGHT, WIDTH
    SENTINEL = 2
    HEIGHT = H + SENTINEL * 2
    WIDTH = W + SENTINEL * 2
    data = [0] * (HEIGHT * WIDTH)
    ok = ord(".")
    for i in range(H):
        S = input().strip()
        y = (i + SENTINEL) * WIDTH
        for j in range(W):
            data[y + (j + SENTINEL)] = 1 if S[j] == ok else 0
    return data


def main():
    
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    D = readMap(H, W)
    print(solve(H, W, Ch, Cw, Dh, Dw, D))



T1 = """
4 4
1 1
4 4
..
..
.
.
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1
"""

T2 = """
4 4
1 4
4 1
.


.
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
-1
"""

T3 = """
4 4
2 2
3 3
....
....
....
....
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
0
"""

T4 = """
4 5
1 2
2 5




"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
2
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**6)

readline = 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 = [readline().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 collections import deque

d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
d_ = [-2, -1, 0, 1, 2]

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [input() for i in range(h)]
INF = 10 ** 6

ch, cw = ch - 1, cw - 1
dh, dw = dh - 1, dw - 1
used = [[INF] * w for i in range(h)]

used[ch][cw] = 0
val = 0
q = deque([(ch, cw, val)])
while q:
    i, j, val = q.popleft()
    if val > used[i][j]:
        continue
    val = used[i][j]

    for di, dj in d:
        nx_i, nx_j = i + di, j + dj
        if not(0 <= nx_i < h and 0 <= nx_j < w):
            continue
        elif s[nx_i][nx_j] == "
            continue
        elif used[nx_i][nx_j] > val:
                used[nx_i][nx_j] = val
                q.appendleft((nx_i, nx_j, val))

    for di in d_:
        for dj in d_:
            nx_i, nx_j = i + di, j + dj
            if not(0 <= nx_i < h and 0 <= nx_j < w):
                continue
            elif s[nx_i][nx_j] == "
                continue
            elif used[nx_i][nx_j] > val + 1:
                used[nx_i][nx_j] = val + 1
                q.append((nx_i, nx_j, val + 1))

if used[dh][dw] == INF:
    print(-1)
else:
    print(used[dh][dw])

Solution (Python):
import sys
sys.setrecursionlimit(500000) 
input = sys.stdin.readline
from collections import deque
H,W = map(int,input().split())
C = list(map(int,input().split()))
C[0] -= 1; C[1] -= 1
D = list(map(int,input().split()))
D[0] -= 1; D[1] -= 1
S = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp =list(temp)
  S.append(temp)

reach = [[INF]*W for _ in range(H)]
reach[C[0]][C[1]] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([])
Q.append([C,0])
while Q:
  z, score = Q.popleft()
  x = z[0];y=z[1]
 
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    
    if 0<=nx<H and 0<=ny<W and S[nx][ny] == "." and reach[nx][ny] > score:
      reach[nx][ny] = min(score,reach[nx][ny])
      u = [nx,ny]
      Q.appendleft([u,score])
  
 
  for i in range(5): 
    for j in range(5):
      mx = x-2 + i
      my = y-2 + j
      if i == 2 and j == 2:
        continue
      if mx < 0 or mx >= H or my < 0 or my >= W or S[mx][my] == "
        continue
      if reach[mx][my] <= score+1: 
        continue
      reach[mx][my] = min(score+1,reach[mx][my])
      p = [mx,my]
      
      Q.append([p,score+1])



if reach[D[0]][D[1]] == INF:
  print(-1)
else:
  print(reach[D[0]][D[1]])

Solution (Python):
from heapq import heappush, heappop
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() for _ in range(h)]

INF = 10**10
cost = [[INF] * w for _ in range(h)]
dx = [+1, 0, -1, 0]
dy = [0, +1, 0, -1]
dxy2 = []
dxy2 += [(i, j) for i in [-2, 2] for j in range(-2, 3)]
dxy2 += [(i, j) for j in [-2, 2] for i in range(-1, 2)]
dxy2 += [(-1, -1), (-1, +1), (+1, -1), (+1, +1)]
q = [(0, ch, cw)]
cost[ch][cw] = 0
while q:
    c, x, y = heappop(q)
    if cost[x][y] < c:
        continue

    if x == dh and y == dw:
        break

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if s[nx][ny] == '
            continue
        if cost[nx][ny] <= c:
            continue
        cost[nx][ny] = c
        heappush(q, (c, nx, ny))

    for dx_, dy_ in dxy2:
        nx = x + dx_
        ny = y + dy_
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if s[nx][ny] == '
            continue
        if cost[nx][ny] <= c + 1:
            continue
        cost[nx][ny] = c + 1
        heappush(q, (c + 1, nx, ny))

ans = -1 if cost[dh][dw] == INF else cost[dh][dw]
print(ans)

Solution (Python):
H, W = map(int, input().split())
C = list(map(lambda x: int(x) - 1, input().split()))
D = list(map(lambda x: int(x) - 1, input().split()))
S = [input() for _ in range(H)]
toGo = [[False if i != C[0] or j != C[1] else True for j in range(W)] for i in range(H)]
queue, mahou = [C], [C]
ans = 0

while True:
    tmp = queue.pop()
    mahou.append(tmp)
    dfs = [tmp]

    while len(dfs):
        a = dfs.pop()
        for move in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            hh, ww = a[0] + move[0], a[1] + move[1]
            if hh >= H or hh < 0 or ww >= W or ww < 0:
                continue

            if not toGo[hh][ww] and S[hh][ww] == '.':
                toGo[hh][ww] = True
                dfs.append([hh, ww])
                mahou.append([hh, ww])

    if toGo[D[0]][D[1]]:
        break

    flag = True
    if not len(queue):
        ans += 1
        for k in mahou:
            for i in range(-2, 3):
                for j in range(-2, 3):
                    h, w = i + k[0], j + k[1]
                    if h >= H or h < 0 or w >= W or w < 0:
                        continue

                    if not toGo[h][w] and S[h][w] == '.':
                        flag = False
                        toGo[h][w] = True
                        queue.append([h, w])
        mahou = []

        if flag:
            print(-1)
            exit()

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1<<20)
h,w=[int(x) for x in input().split()]
ch,cw=[int(x) for x in input().split()]
dh,dw=[int(x) for x in input().split()]
ch-=1
cw-=1
dh-=1
dw-=1

s=[]
for _ in range(h):
    s.append(list(input()))

nxt=[[ch,cw,0]]

def rcl(y,x,now):
    
    if y==dh and x==dw:
        print(now)
        exit()
    
    if s[y][x]=='
        return
    
    s[y][x]='
    
    for i in range(4):
        yy,xx=-1,0
        if i==1:yy,xx=0,1
        if i==2:yy,xx=1,0
        if i==3:yy,xx=0,-1
        
        if y+yy<0 or h<=y+yy or x+xx<0 or w<=x+xx:
            continue
        if s[y+yy][x+xx]=='
            continue
        
        rcl(y+yy,x+xx,now)
    
    for i in range(-2,3):
        for j in range(-2,3):
            if i==0 and j==0:
                continue
            if y+i<0 or h<=y+i or x+j<0 or w<=x+j:
                continue
            if s[y+i][x+j]=='.':
                nxt.append([y+i,x+j,now+1])
                s[y+i][x+j]=now+1


while nxt:
    i=nxt.pop(0)
    if i[0]==dh and i[1]==dw:
        print(i[2])
        exit()
    rcl(i[0],i[1],i[2])
print(-1)

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


from heapq import heappush, heappop

input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

H, W = rl()
C = rl()
D = rl()
M = []
for i in range(H):
	s = rs()
	M.append(s)

start = tuple([C[0]-1, C[1]-1])
end = tuple([D[0]-1, D[1]-1])

queue = deque()
queue.append((start, 0))
visited = defaultdict(lambda: float('inf'))
visited[start] = 0

while queue:
	n, d = queue.popleft()
	if n == end:
		print(d)
		exit()
	if visited[n] != d:
		continue
	i, j = n
	for di in range(-2, 3):
		for dj in range(-2, 3):
			if (di, dj) == (0,0): continue
			ni, nj = i+di, j+dj
			if not (0 <= ni < H and 0 <= nj < W): continue
			if M[ni][nj] == '
			if (di, dj) in [(1,0),(-1,0),(0,1),(0,-1)]:
				nd = d
				if nd < visited[(ni,nj)]:
					queue.appendleft(((ni,nj), nd))
					visited[(ni,nj)] = nd
			else:
				nd = d+1
				if nd < visited[(ni,nj)]:
					queue.append(((ni,nj), nd))
					visited[(ni,nj)] = nd
print(-1)

Solution (Python):
import sys, math



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

while len(next_que)>0 or len(que)>0:
    while len(que)>0:
        c, h, w = que.pop(0)
        if c >= costs[Dh-1][Dw-1]:
            print(costs[Dh-1][Dw-1])
            sys.exit()
        for i, j in [(h-1, w), (h+1, w), (h, w-1), (h, w+1)]:
            if i < 0 or j < 0 or i>=H or j>=W:
                continue
            if i == Dh - 1 and j == Dw - 1:
                print(c)
                sys.exit()
            if S[i][j] and costs[i][j] > c:
                costs[i][j] = c
                que.append((c, i, j))
        for dw in [-2, -1, 0, 1, 2]:
            for dh in [-2, -1, 0, 1, 2]:
                if w+dw < 0 or h+dh < 0 or w+dw>=W or h+dh>=H:
                    continue
                if S[h+dh][w+dw] and costs[h+dh][w+dw] > c+1:
                    costs[h+dh][w+dw] = c+1
                    next_que.append((c+1, h+dh, w+dw))
    que = next_que
    next_que = []

print(-1)

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

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

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

answer = 0

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)
                    exit()
                grid[nh][nw] = 1
                stack1.append((nh, nw))
    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)
                        exit()
                    grid[nh][nw] = 1
                    stack1.append((nh, nw))
    if not stack1:
        print(-1)
        exit()

Solution (Python):
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import sys
import numpy as np

def solve(H, W, Cy, Cx, Dy, Dx, S):
    inf = 1<<60
    Cy -= 1
    Cx -= 1
    Dy -= 1
    Dx -= 1
    st0 = [(Cy,Cx,0)]
    st1 = [(0,0,0)]*0
    D = np.full((H, W), inf)
    D[Cy, Cx] = 0
    while st0 or st1:
        if not st0:
            st0 = st1
            st1 = [(0,0,0)]*0
        y, x, d = st0.pop()
        if D[y, x] != d:
            continue
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                uy = y + dy
                ux = x + dx
                if 0<=uy<H and 0<=ux<W and S[uy,ux]==0:
                    if abs(dy)+abs(dx) <= 1:
                        if D[uy, ux] > d:
                            st0.append((uy, ux, d))
                            D[uy, ux] = d
                    else:
                        if D[uy, ux] > d + 1:
                            st1.append((uy, ux, d+1))
                            D[uy, ux] = d+1
    ans = D[Dy, Dx] if D[Dy, Dx] != inf else -1
    return ans

numba_compile([
    [solve, "i8(i8,i8,i8,i8,i8,i8,u1[:,:])"]
])

def main():
    H, W = map(int, sys.stdin.buffer.readline().split())
    Cy, Cx = map(int, sys.stdin.buffer.readline().split())
    Dy, Dx = map(int, sys.stdin.buffer.readline().split())
    S = np.empty((H, W), dtype=np.uint8)
    for i in range(H):
        S[i] = np.frombuffer(sys.stdin.buffer.readline()[:-1], dtype=np.uint8) == ord("
    ans = solve(H, W, Cy, Cx, Dy, Dx, S)
    print(ans)

main()

Solution (Python):
from collections import deque
def bfs(sl, visited, sy, sx, gy, gx, h, w):
    q = deque([(sy,sx,0)])
    q_warp = deque([])
    visited[sy][sx] = 0

    while q:
        while q:
            y, x, d = q.popleft()
            if (y, x) == (gy, gx):
                return visited[gy][gx]
            for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                ny, nx = y+j, x+k
                if ny >= h or nx >= w or ny < 0 or nx < 0:
                    continue
                if sl[ny][nx] == '.' and (visited[ny][nx] == -1 or visited[ny][nx] > visited[y][x]):
                    visited[ny][nx] = visited[y][x]
                    q.appendleft((ny,nx,d))

            for j in range(-2,3):
                for k in range(-2,3):
                    ny, nx = y+j, x+k
                    if ny >= h or nx >= w or ny < 0 or nx < 0: continue
                    if sl[ny][nx] == '.' and visited[ny][nx] == -1:
                        visited[ny][nx] = visited[y][x] + 1
                        q.append((ny,nx,d))

    return -1


h, w = map(int, input().split()) 
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
sl = [list(input()) for _ in range(h)]
visited = [ [-1]*w for i in range(h)]
ans = bfs(sl,visited,ch-1,cw-1,dh-1,dw-1,h,w)
print(ans)

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 -= 1
Cw -= 1
Dh -= 1
Dw -= 1

WALL = -100
INI = -1
PASSED = 0

S = [[0] * w for _ in range(h)]
for i in range(h):
    tmp = input()
    for j in range(w):
        if tmp[j] == '
            S[i][j] = WALL
        else:
            S[i][j] = INI

S[Ch][Cw] = 0
direction = [[0, -1], [-1, 0], [0, 1], [1, 0]]


def dfs(y, x, d):
    d.append((y, x))
    if y == Dh and x == Dw:
        print(S[y][x])
        exit()
    for dy, dx in direction:
        next_y = y + dy
        next_x = x + dx
        if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w:
            continue
        if S[next_y][next_x] == INI:
            
            S[next_y][next_x] = S[y][x]
            dfs(next_y, next_x, d)

def bfs(y, x, d):
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            next_y = y + dy
            next_x = x + dx
            if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w:
                continue
            if S[next_y][next_x] == INI:
                d.append((next_y, next_x))
                
                S[next_y][next_x] = S[y][x] + 1
    return False

def show(S):
    for y in range(h):
        for x in range(w):
            if S[y][x] == WALL:
                print("
            elif S[y][x] == INI:
                print(".", end="")
            else:
                print(S[y][x], end="")
        print()

d = deque()
d.append((Ch, Cw))
d2 = deque()
while len(d):
    while(len(d)):
        y, x = d.popleft()
        dfs(y, x, d2)

    while len(d2):
        y2, x2 = d2.popleft()
        
        
        bfs(y2, x2, d)

print(-1)

Solution (Python):

import sys
from collections import deque
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(H, W, Ch, Cw, Dh, Dw, data):
    
    N = HEIGHT * WIDTH
    visited = [0] * N

    start = (Ch + 1) * WIDTH + (Cw + 1)
    goal = (Dh + 1) * WIDTH + (Dw + 1)
    q = []
    nextJump = set()
    q.append(start)

    currentDistance = 0
    while True:
        while q:
            p = q.pop()
            if p == goal:
                return currentDistance
            if visited[p]:
                continue
            for dx in [-2, -1, 0, +1, +2]:
                for dy in [-WIDTH * 2, -WIDTH, 0, WIDTH, WIDTH * 2]:
                    nextJump.add(p + dx + dy)
            visited[p] = 1
            for d in [-1, +1, -WIDTH, +WIDTH]:
                if data[p + d] and not visited[p + d]:
                    q.append(p + d)

        
        for p in nextJump:
            if not data[p]:
                continue
            if visited[p]:
                continue
            q.append(p)

        currentDistance += 1
        nextJump = set()
        if not q:
            return -1


def readMap(H, W):
    global SENTINEL, HEIGHT, WIDTH
    SENTINEL = 2
    HEIGHT = H + SENTINEL * 2
    WIDTH = W + SENTINEL * 2
    data = [0] * (HEIGHT * WIDTH)
    ok = ord(".")
    for i in range(H):
        S = input().strip()
        y = (i + SENTINEL) * WIDTH
        for j in range(W):
            data[y + (j + SENTINEL)] = 1 if S[j] == ok else 0
    return data


def main():
    
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    D = readMap(H, W)
    print(solve(H, W, Ch, Cw, Dh, Dw, D))



T1 = """
4 4
1 1
4 4
..
..
.
.
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1
"""

T2 = """
4 4
1 4
4 1
.


.
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
-1
"""

T3 = """
4 4
2 2
3 3
....
....
....
....
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
0
"""

T4 = """
4 5
1 2
2 5




"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
2
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij4=[(0,1),(1,0),(-1,0),(0,-1)]

def solve():
    aa = [[-1] * w for _ in range(h)]
    stack = [(si, sj, 0)]

    while stack:
        wall = []
        while stack:
            i, j, d = stack.pop()
            crash = False
            for di, dj in dij4:
                ni, nj = i + di, j + dj
                if ni < 0 or ni >= h or nj < 0 or nj >= w: continue
                if aa[ni][nj] != -1: continue
                if ss[ni][nj]: crash = True
                else:
                    aa[ni][nj] = d
                    stack.append((ni, nj, d))
            if crash: wall.append((i, j, d))

        for i, j, d in wall:
            for di in range(-2, 3):
                for dj in range(-2, 3):
                    if di == 0 and dj == 0: continue
                    ni, nj = i + di, j + dj
                    if ni < 0 or ni >= h or nj < 0 or nj >= w: continue
                    if ss[ni][nj]: continue
                    if aa[ni][nj] != -1: continue
                    aa[ni][nj] = d + 1
                    stack.append((ni, nj, d + 1))

    print(aa[gi][gj])

h,w=MI()
si,sj=MI1()
gi,gj=MI1()
ss=[[1 if c=="
solve()