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

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


def read():
    H, W = map(int, input().strip().split())
    CH, CW = map(int, input().strip().split())
    DH, DW = map(int, input().strip().split())
    S = [[0 for j in range(W)] for i in range(H)]
    for i in range(H):
        s = list(input().strip())
        for j in range(W):
            if s[j] == "
                S[i][j] = -2
            else:
                S[i][j] = -1
    return H, W, CH, CW, DH, DW, S


def solve(H, W, CH, CW, DH, DW, S):
    DIR0 = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    DIR1 = [
        (-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)
    ]
    S[CH-1][CW-1] = 0
    q = deque()
    q.appendleft((CH-1, CW-1))
    while q:
        
        y0, x0 = q.popleft()
        d0 = S[y0][x0]
        
        for dy, dx in DIR0:
            ny, nx = y0 + dy, x0 + dx
            if 0 <= ny < H and 0 <= nx < W and (S[ny][nx] == -1 or S[ny][nx] > d0):
                q.appendleft((ny, nx))
                S[ny][nx] = d0
        
        for dy, dx in DIR1:
            ny, nx = y0 + dy, x0 + dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == -1:
                q.append((ny, nx))
                S[ny][nx] = d0+1
    return S[DH-1][DW-1]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

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

lim = 10**6

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

foo = [[-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] == '.':
      foo[k][j] = lim
    

foo[Ch][Cw] = 0

now = deque([])
new = deque([(Ch, Cw)])
while len(new) > 0:
  item = new.pop()
  now.append(item)
  x = item[0]
  y = item[1]
  if foo[x+1][y] == lim:
    foo[x+1][y] = 0
    new.append((x+1, y))
  if foo[x][y+1] == lim:
    foo[x][y+1] = 0
    new.append((x, y+1))
  if foo[x-1][y] == lim:
    foo[x-1][y] = 0
    new.append((x-1, y))
  if foo[x][y-1] == lim:
    foo[x][y-1] = 0
    new.append((x, y-1))


ans = 0
while foo[Dh][Dw] == lim:
  if len(now) == 0:
    print(-1)
    exit() 
  ans += 1
  while len(now) > 0:
    item = now.pop()
    x = item[0]
    y = item[1]
    if foo[x+2][y+2] > ans:
      foo[x+2][y+2] = ans
      new.append((x+2, y+2))
    if foo[x+2][y+1] > ans:
      foo[x+2][y+1] = ans
      new.append((x+2, y+1))
    if foo[x+2][y] > ans:
      foo[x+2][y] = ans
      new.append((x+2, y))
    if foo[x+2][y-1] > ans:
      foo[x+2][y-1] = ans
      new.append((x+2, y-1))
    if foo[x+2][y-2] > ans:
      foo[x+2][y-2] = ans
      new.append((x+2, y-2))
    if foo[x+1][y+2] > ans:
      foo[x+1][y+2] = ans
      new.append((x+1, y+2))
    if foo[x+1][y-2] > ans:
      foo[x+1][y-2] = ans
      new.append((x+1, y-2))
    if foo[x][y+2] > ans:
      foo[x][y+2] = ans
      new.append((x, y+2))
    if foo[x][y-2] > ans:
      foo[x][y-2] = ans
      new.append((x, y-2))
    if foo[x-2][y+2] > ans:
      foo[x-2][y+2] = ans
      new.append((x-2, y+2))
    if foo[x-2][y+1] > ans:
      foo[x-2][y+1] = ans
      new.append((x-2, y+1))
    if foo[x-2][y] > ans:
      foo[x-2][y] = ans
      new.append((x-2, y))
    if foo[x-2][y-1] > ans:
      foo[x-2][y-1] = ans
      new.append((x-2, y-1))
    if foo[x-2][y-2] > ans:
      foo[x-2][y-2] = ans
      new.append((x-2, y-2))
    if foo[x-1][y+2] > ans:
      foo[x-1][y+2] = ans
      new.append((x-1, y+2))
    if foo[x-1][y-2] > ans:
      foo[x-1][y-2] = ans
      new.append((x-1, y-2))
    if foo[x-1][y-1] > ans:
      foo[x-1][y-1] = ans
      new.append((x-1, y-1))
    if foo[x-1][y+1] > ans:
      foo[x-1][y+1] = ans
      new.append((x-1, y+1))
    if foo[x+1][y+1] > ans:
      foo[x+1][y+1] = ans
      new.append((x+1, y+1))
    if foo[x+1][y-1] > ans:
      foo[x+1][y-1] = ans
      new.append((x+1, y-1))
      
  while len(new) > 0:
    item = new.pop()
    now.append(item)
    x = item[0]
    y = item[1]
    if foo[x+1][y] == lim:
      foo[x+1][y] = 0
      new.append((x+1, y))
    if foo[x][y+1] == lim:
      foo[x][y+1] = 0
      new.append((x, y+1))
    if foo[x-1][y] == lim:
      foo[x-1][y] = 0
      new.append((x-1, y))
    if foo[x][y-1] == lim:
      foo[x][y-1] = 0
      new.append((x, y-1))
print(ans)

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


def read():
    H, W = map(int, input().strip().split())
    CH, CW = map(int, input().strip().split())
    DH, DW = map(int, input().strip().split())
    S = [[0 for j in range(W)] for i in range(H)]
    for i in range(H):
        s = list(input().strip())
        for j in range(W):
            if s[j] == "
                S[i][j] = -2
            else:
                S[i][j] = -1
    return H, W, CH, CW, DH, DW, S


def solve(H, W, CH, CW, DH, DW, S):
    DIR0 = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    DIR1 = [(y, x) for y, x in product(range(-2, 3), range(-2, 3))]
    S[CH-1][CW-1] = 0
    q = deque()
    q.append((CH-1, CW-1))
    while q:
        y0, x0 = q.popleft()
        d0 = S[y0][x0]
        
        T = []
        r = deque()
        T.append((y0, x0))
        r.append((y0, x0))
        while r:
            y, x = r.popleft()
            for dy, dx in DIR0:
                ny, nx = y + dy, x + dx
                if 0 <= ny < H and 0 <= nx < W and (S[ny][nx] == -1 or S[ny][nx] > d0):
                    r.append((ny, nx))
                    T.append((ny, nx))
                    S[ny][nx] = d0
        
        for y, x in T:
            for dy, dx in DIR1:
                ny, nx = y + dy, x + dx
                if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == -1:
                    q.append((ny, nx))
                    S[ny][nx] = d0+1
    return S[DH-1][DW-1]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Solution (Python):
import heapq
class Dijkstra:
    INF = 1 << 63

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost): self.G[X].append((cost << 31) + Y)

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, st)
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)
            cost = p >> 31
            node = p - (cost << 31)
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to >> 31
                to_node = to - (to_cost << 31)
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, (to_cost << 31) + to_node)

h, w = map(int, input().split())
sh, sw = map(int, input().split())
eh, ew = map(int, input().split())

sh -= 1
sw -= 1
eh -= 1
ew -= 1

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

di = Dijkstra(h*w)
for x in range(h):
    for y in range(w):
        if S[x][y] == '
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + i
                Y = y + j
                if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '
                D = abs(i) + abs(j)

                if D == 1: di.insert(x * w + y, X * w + Y, 0)
                if D >= 2: di.insert(x * w + y, X * w + Y, 1)

di.dijkstra(sh * w + sw)
ans = di.dist[eh * w + ew]
if ans == (1 << 63): print(-1)
else: print(ans)

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


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

foo = [[-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] == '.':
      foo[k][j] = 10**6

foo[Ch][Cw] = 0

now = []
new = [(Ch, Cw)]
while len(new) > 0:
  item = new.pop()
  now.append(item)
  x = item[0]
  y = item[1]
  if foo[x+1][y] == 10**6:
    foo[x+1][y] = 0
    new.append((x+1, y))
  if foo[x][y+1] == 10**6:
    foo[x][y+1] = 0
    new.append((x, y+1))
  if foo[x-1][y] == 10**6:
    foo[x-1][y] = 0
    new.append((x-1, y))
  if foo[x][y-1] == 10**6:
    foo[x][y-1] = 0
    new.append((x, y-1))


ans = 0
while foo[Dh][Dw] == 10**6:
  if len(now) == 0:
    print(-1)
    exit() 
  ans += 1
  while len(now) > 0:
    item = now.pop()
    x = item[0]
    y = item[1]
    if foo[x+2][y+2] > ans:
      foo[x+2][y+2] = ans
      new.append((x+2, y+2))
    if foo[x+2][y+1] > ans:
      foo[x+2][y+1] = ans
      new.append((x+2, y+1))
    if foo[x+2][y] > ans:
      foo[x+2][y] = ans
      new.append((x+2, y))
    if foo[x+2][y-1] > ans:
      foo[x+2][y-1] = ans
      new.append((x+2, y-1))
    if foo[x+2][y-2] > ans:
      foo[x+2][y-2] = ans
      new.append((x+2, y-2))
    if foo[x+1][y+2] > ans:
      foo[x+1][y+2] = ans
      new.append((x+1, y+2))
    if foo[x+1][y-2] > ans:
      foo[x+1][y-2] = ans
      new.append((x+1, y-2))
    if foo[x][y+2] > ans:
      foo[x][y+2] = ans
      new.append((x, y+2))
    if foo[x][y-2] > ans:
      foo[x][y-2] = ans
      new.append((x, y-2))
    if foo[x-2][y+2] > ans:
      foo[x-2][y+2] = ans
      new.append((x-2, y+2))
    if foo[x-2][y+1] > ans:
      foo[x-2][y+1] = ans
      new.append((x-2, y+1))
    if foo[x-2][y] > ans:
      foo[x-2][y] = ans
      new.append((x-2, y))
    if foo[x-2][y-1] > ans:
      foo[x-2][y-1] = ans
      new.append((x-2, y-1))
    if foo[x-2][y-2] > ans:
      foo[x-2][y-2] = ans
      new.append((x-2, y-2))
    if foo[x-1][y+2] > ans:
      foo[x-1][y+2] = ans
      new.append((x-1, y+2))
    if foo[x-1][y-2] > ans:
      foo[x-1][y-2] = ans
      new.append((x-1, y-2))
    if foo[x-1][y-1] > ans:
      foo[x-1][y-1] = ans
      new.append((x-1, y-1))
    if foo[x-1][y+1] > ans:
      foo[x-1][y+1] = ans
      new.append((x-1, y+1))
    if foo[x+1][y+1] > ans:
      foo[x+1][y+1] = ans
      new.append((x+1, y+1))
    if foo[x+1][y-1] > ans:
      foo[x+1][y-1] = ans
      new.append((x+1, y-1))
      
  while len(new) > 0:
    item = new.pop()
    now.append(item)
    x = item[0]
    y = item[1]
    if foo[x+1][y] == 10**6:
      foo[x+1][y] = 0
      new.append((x+1, y))
    if foo[x][y+1] == 10**6:
      foo[x][y+1] = 0
      new.append((x, y+1))
    if foo[x-1][y] == 10**6:
      foo[x-1][y] = 0
      new.append((x-1, y))
    if foo[x][y-1] == 10**6:
      foo[x][y-1] = 0
      new.append((x, y-1))
print(ans)

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


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

foo = [[-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] == '.':
      foo[k][j] = 10**6

foo[Ch][Cw] = 0

now = []
new = [(Ch, Cw)]
while len(new) > 0:
  item = new.pop()
  now.append(item)
  x = item[0]
  y = item[1]
  if foo[x+1][y] == 10**6:
    foo[x+1][y] = 0
    new.append((x+1, y))
  if foo[x][y+1] == 10**6:
    foo[x][y+1] = 0
    new.append((x, y+1))
  if foo[x-1][y] == 10**6:
    foo[x-1][y] = 0
    new.append((x-1, y))
  if foo[x][y-1] == 10**6:
    foo[x][y-1] = 0
    new.append((x, y-1))


ans = 0
while foo[Dh][Dw] == 10**6:
  if len(now) == 0:
    print(-1)
    exit() 
  ans += 1
  while len(now) > 0:
    item = now.pop()
    x = item[0]
    y = item[1]
    if foo[x+2][y+2] > ans:
      foo[x+2][y+2] = ans
      new.append((x+2, y+2))
    if foo[x+2][y+1] > ans:
      foo[x+2][y+1] = ans
      new.append((x+2, y+1))
    if foo[x+2][y] > ans:
      foo[x+2][y] = ans
      new.append((x+2, y))
    if foo[x+2][y-1] > ans:
      foo[x+2][y-1] = ans
      new.append((x+2, y-1))
    if foo[x+2][y-2] > ans:
      foo[x+2][y-2] = ans
      new.append((x+2, y-2))
    if foo[x+1][y+2] > ans:
      foo[x+1][y+2] = ans
      new.append((x+1, y+2))
    if foo[x+1][y-2] > ans:
      foo[x+1][y-2] = ans
      new.append((x+1, y-2))
    if foo[x][y+2] > ans:
      foo[x][y+2] = ans
      new.append((x, y+2))
    if foo[x][y-2] > ans:
      foo[x][y-2] = ans
      new.append((x, y-2))
    if foo[x-2][y+2] > ans:
      foo[x-2][y+2] = ans
      new.append((x-2, y+2))
    if foo[x-2][y+1] > ans:
      foo[x-2][y+1] = ans
      new.append((x-2, y+1))
    if foo[x-2][y] > ans:
      foo[x-2][y] = ans
      new.append((x-2, y))
    if foo[x-2][y-1] > ans:
      foo[x-2][y-1] = ans
      new.append((x-2, y-1))
    if foo[x-2][y-2] > ans:
      foo[x-2][y-2] = ans
      new.append((x-2, y-2))
    if foo[x-1][y+2] > ans:
      foo[x-1][y+2] = ans
      new.append((x-1, y+2))
    if foo[x-1][y-2] > ans:
      foo[x-1][y-2] = ans
      new.append((x-1, y-2))
    if foo[x-1][y-1] > ans:
      foo[x-1][y-1] = ans
      new.append((x-1, y-1))
    if foo[x-1][y+1] > ans:
      foo[x-1][y+1] = ans
      new.append((x-1, y+1))
    if foo[x+1][y+1] > ans:
      foo[x+1][y+1] = ans
      new.append((x+1, y+1))
    if foo[x+1][y-1] > ans:
      foo[x+1][y-1] = ans
      new.append((x+1, y-1))
      
  while len(new) > 0:
    item = new.pop()
    now.append(item)
    x = item[0]
    y = item[1]
    if foo[x+1][y] == 10**6:
      foo[x+1][y] = 0
      new.append((x+1, y))
    if foo[x][y+1] == 10**6:
      foo[x][y+1] = 0
      new.append((x, y+1))
    if foo[x-1][y] == 10**6:
      foo[x-1][y] = 0
      new.append((x-1, y))
    if foo[x][y-1] == 10**6:
      foo[x][y-1] = 0
      new.append((x, y-1))
print(ans)

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

class Dijkstra:
    INF = 10**18
    threshold = 10**9

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost): self.G[X].append(cost * self.threshold + Y)

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, st)
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)
            cost = p // self.threshold
            node = p - cost * self.threshold
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to // self.threshold
                to_node = to - to_cost * self.threshold
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, to_cost * self.threshold + to_node)

h, w = map(int, input().split())
sh, sw = map(int, input().split())
eh, ew = map(int, input().split())

sh -= 1
sw -= 1
eh -= 1
ew -= 1

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

di = Dijkstra(h*w)
for x in range(h):
    for y in range(w):
        if S[x][y] == '
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + i
                Y = y + j
                if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '
                D = abs(i) + abs(j)

                if D == 1: di.insert(x * w + y, X * w + Y, 0)
                if D >= 2: di.insert(x * w + y, X * w + Y, 1)

di.dijkstra(sh * w + sw)
ans = di.dist[eh * w + ew]
if ans == 10**18: print(-1)
else: 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, cw, dh, dw = ch-1, cw-1, dh-1, dw-1
s = [list(input()) for _ in range(h)]

def bfs(sy, sx):
    que = deque([])
    que.append([sy, sx])

    while que:
        y, x = que.popleft()
        dx, dy = [0,1,0,-1], [1,0,-1,0]
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if ny < 0 or ny >= h or nx < 0 or nx >= w: continue
            if s[ny][nx] == '
            if seen[ny][nx] != -1: continue
            
            seen[ny][nx] = seen[y][x]
            que.append([ny, nx])
            wp.append([ny, nx])

            
dq = deque([])
dq.append([ch, cw])
seen = [[-1]*w for _ in range(h)]
seen[ch][cw] = 0
wp = deque([])
while dq:
    while dq:
        y, x = dq.popleft()
        wp.append([y, x])
        bfs(y, x)

    ok = False
    while wp:
        y, x = wp.popleft()
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                if dy == 0 and dx == 0: continue
                ny, nx = y+dy, x+dx
                if ny < 0 or ny >= h or nx < 0 or nx >= w: continue
                if s[ny][nx] == '
                if seen[ny][nx] >= 0: continue

                ok = True
                seen[ny][nx] = seen[y][x] + 1
                dq.append([ny, nx])

    if not ok: break

if seen[dh][dw] >= 0:
    print(seen[dh][dw])
else:
    print(-1)

Solution (Python):
import heapq
class Dijkstra:
    INF = 10**18
    threshold = 10**9

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost): self.G[X].append(cost * self.threshold + Y)

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, st)
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)
            cost = p // self.threshold
            node = p - cost * self.threshold
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to // self.threshold
                to_node = to - to_cost * self.threshold
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, to_cost * self.threshold + to_node)

h, w = map(int, input().split())
sh, sw = map(int, input().split())
eh, ew = map(int, input().split())

sh -= 1
sw -= 1
eh -= 1
ew -= 1

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

di = Dijkstra(h*w)
for x in range(h):
    for y in range(w):
        if S[x][y] == '
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + i
                Y = y + j
                if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '
                D = abs(i) + abs(j)

                if D == 1: di.insert(x * w + y, X * w + Y, 0)
                if D >= 2: di.insert(x * w + y, X * w + Y, 1)

di.dijkstra(sh * w + sw)
ans = di.dist[eh * w + ew]
if ans == 10**18: print(-1)
else: print(ans)

Solution (Python):
H, W = map(int, input().split())
sx, sy = map(int, input().split())
sx -= 1; sy -= 1
tx, ty = map(int, input().split())
tx -= 1; ty -= 1

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


dxy = [(-1, 0), (0, -1), (1, 0), (0, 1)]
dist = {}
next_points = set([(sx, sy)])
def bfs(d):
    global dist, next_points
    stack = list(next_points)
    next_points = set()
    while stack:
        x, y = stack.pop()
        if (x, y) in dist and dist[(x, y)] < d:
            continue
        dist[(x, y)] = d
        count = 0
        for dx, dy in dxy:
            xx = x + dx; yy = y + dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy] == '.':
                count += 1
                if (xx, yy) not in dist:
                    dist[(xx, yy)] = d
                    stack.append((xx, yy))
        
        if count < 4:
            for dx in range(-2, 3):
                xx = x + dx
                for dy in range(-2, 3):
                    yy = y + dy
                    if (xx, yy) not in dist and 0 <= xx < H and 0 <= yy < W \
                            and S[xx][yy] == '.':
                        next_points.add((xx, yy))

d = 0
while (tx, ty) not in dist:
    bfs(d)
    d += 1
    if len(next_points) == 0:
        if (tx, ty) in dist:
            print(dist[(tx, ty)])
        else:
            print(-1)
        quit()

print(dist[(tx, ty)])

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 = [None]*(H+4)
S[0] = S[1] = S[H+2] = S[H+3] = ["
for i in range(2, H+2):
    S[i] = ["

cost = [[-1 for _ in range(W+3)] for _ in range(H+3)]

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



warp_times = 0

def warp(i, j, cost, warp_times, q):
    change = 0
    for h in range(i-2, i+3):
        for w in range(j-2, j+3):
            
            
            if S[h][w] == "." and cost[h][w] == -1:
                q.append([h, w])
                cost[h][w] = warp_times + 1
                change = 1
    
    return change

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

while True:
    

    same_cost = list()
    no_change = 1

    while len(q):
        
        now = q.popleft()
        i = now[0]
        j = now[1]

        cost[i][j] = warp_times
        same_cost.append([i, j])

        if S[i][j-1] == "." and cost[i][j-1] == -1:
            q.append([i, j-1])
            cost[i][j-1] = warp_times
        if S[i][j+1] == "." and cost[i][j+1] == -1:
            q.append([i, j+1])
            cost[i][j+1] = warp_times
        if S[i-1][j] == "." and cost[i-1][j] == -1:
            q.append([i-1, j])
            cost[i-1][j] = warp_times
        if S[i+1][j] == "." and cost[i+1][j] == -1:
            q.append([i+1, j])
            cost[i-1][j] = warp_times
    

    for point in same_cost:
        change = warp(point[0], point[1], cost, warp_times, q)
        if change :
            no_change = 0
    
    warp_times += 1
    
    if no_change:
        break

print(cost[Dh][Dw])

Solution (Python):
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)
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
      
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

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):
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

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 = "

@njit((b1[:, :],i8,i8,i8,i8), cache=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
ss = np.array([[c=="

print(main(ss,ch,cw,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

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=="


@njit((b1[:, :],i8,i8,i8,i8), cache=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

print(main(ss,ch,cw,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), cache=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):
import sys
input = sys.stdin.readline
import collections
def bfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dx2 = [(-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 len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == ".":
                    if dist[h2][w2] == -1:
                        dist[h2][w2] = d
                        q.appendleft((h2, w2))
                    elif d < dist[h2][w2]:
                        dist[h2][w2] = d
                        q.appendleft((h2, w2))
        for x, y in dx2:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == "." and (dist[h2][w2] == -1 or d + 1 < dist[h2][w2]):
                    dist[h2][w2] = d + 1
                    q.append((h2, w2))
    return dist[gy][gx]

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
grid = [input() for _ in range(H)]
print(bfs(Ch-1, Cw-1, Dh-1, Dw-1))