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

    input = sys.stdin.readline

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

    S=[list(map(str,list(input()[:-1]))) for i in range(H)]

    dh = (1, 0, -1, 0)
    dw = (0, 1, 0, -1)
    warph = (2, 2, 2, 2 ,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2)
    warpw = (-2, -1, 0, 1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2)

    d = deque()

    d.append((Ch-1,Cw-1))

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

    while len(d) > 0:
        Ph,Pw = d.popleft()

        
        
        

        for i in range(4):
            nh = Ph + dh[i]
            nw = Pw + dw[i]
            if (nh < 0) | (nh >= H) | (nw < 0) | (nw >= W):
                continue
            if S[nh][nw] == "
                continue
            if S[nh][nw] == ".":
                S[nh][nw] = S[Ph][Pw]
                d.appendleft((nh,nw))
            elif S[nh][nw] > S[Ph][Pw]:
                S[nh][nw] = min(S[nh][nw],S[Ph][Pw])
                d.appendleft((nh,nw))





        for i in range(20):
            nh = Ph + warph[i]
            nw = Pw + warpw[i]
            if (nh < 0) | (nh >= H) | (nw < 0) | (nw >= W):
                continue
            if S[nh][nw] == "
                continue
            if S[nh][nw] == ".":
                S[nh][nw] = S[Ph][Pw] + 1
                d.append((nh,nw))
            elif S[nh][nw] > S[Ph][Pw] + 1:
                S[nh][nw] = min(S[nh][nw],S[Ph][Pw]+1)
                d.append((nh,nw))

    if S[Dh-1][Dw-1] == ".":
        print("-1")
    else:
        print(S[Dh-1][Dw-1])
         

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
import sys
def input():return sys.stdin.readline().strip()
def main():
    H, W = map(int, input().split())
    sh, sw = map(int, input().split())
    sh -= 1; sw -= 1
    start = (sh+2)*(W+4) + 2 + sw
    dh, dw = map(int, input().split())
    dh -= 1; dw -= 1
    goal = (dh+2)*(W+4) + 2 + dw

    field = "
    field += "
    field += "

    move = [-1, 1, -(W+4), W+4]
    ex_left = [-2*(W+4)-2, -(W+4)-2, -2, (W+4)-2, 2*(W+4)-2, -(W+4)-1, (W+4)-1]
    ex_right = [-2*(W+4)+2, -(W+4)+2, +2, (W+4)+2, 2*(W+4)+2, -(W+4)+1, (W+4)+1]
    ex_up = [-2*(W+4)-2, -2*(W+4)-1, -2*(W+4), -2*(W+4)+1, -2*(W+4)+2, -(W+4)-1, -(W+4)+1]
    ex_down = [2*(W+4)-2, 2*(W+4)-1, 2*(W+4), 2*(W+4)+1, 2*(W+4)+2, (W+4)-1, (W+4)+1]

    INF = 10 ** 18
    num = [INF] * (H+4) * (W+4)
    warped = [False] * (H+4) * (W+4)

    def bfs(s):
        q = deque()
        num[s] = 0
        q.append((s, 0))
    
        while q:
            now, cost = q.popleft()

            
            if cost > num[now]:
                continue
            else:
                num[now] = cost

            if now == goal:
                return

            for i, dx in enumerate(move):
                nx = now + dx
                if field[nx] == "." and num[nx] == INF:
                    q.appendleft((nx, cost))
                    num[nx] = cost

                elif field[nx] == "
                    if i == 0:
                        ex = ex_left
                    elif i == 1:
                        ex = ex_right
                    elif i == 2:
                        ex = ex_up
                    else:
                        ex = ex_down

                    for dx2 in ex:
                        nx2 = now + dx2
                        if field[nx2] == "." and num[nx2] == INF and not warped[nx2]:
                            q.append((nx2, cost+1))
                            warped[nx2] = True
    
    bfs(start)

    if num[goal] == INF:
        print(-1)
    else:
        print(num[goal])

    
    
    
    
    
    
    
    
    


if __name__ == "__main__":
    main()

Solution (Python):


import collections

H, W = map(int, input().split())
C = tuple((int(x)-1 for x in input().split()))
D = tuple((int(x)-1 for x in input().split()))
S = list()
for _ in range(H):
    S.append(list(input()))

queue = collections.deque()
visited = collections.deque()
queue.append(C)
cy, cx = C
S[cy][cx] = 0

while len(queue):
    while len(queue):
        y, x = queue.popleft()
        visited.append((y, x))
        cost = S[y][x]
        for i, j in [(y-1, x), (y+1, x), (y, x-1), (y, x+1)]:
            if not (0 <= i < H and 0 <= j < W):
                continue
            if S[i][j] == '.':
                S[i][j] = cost
                queue.append((i, j))

    while len(visited):
        y, x = visited.popleft()
        cost = S[y][x]
        for i in range(y-2, y+2+1):
            for j in range(x-2, x+2+1):
                if not (0 <= i < H and 0 <= j < W):
                    continue
                if S[i][j] == '.':
                    S[i][j] = cost+1
                    queue.append((i, j))

dy, dx = D
result = S[dy][dx]
if result == '.':
    print(-1)
else:
    print(result)

Solution (Python):
from collections import deque
import math
 
def explore(C, D):
    queue = deque([(C[0]-1, C[1]-1)])
    maze_visited[C[0]-1][C[1]-1] = 0
    while queue:
        y, x = queue.popleft()
        mv_cur = maze_visited[y][x]
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            n_x, n_y = x + i, y + j
            if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                mv_n = maze_visited[n_y][n_x]
                if mv_n > mv_cur:
                    if S[n_y][n_x] == '.':
                        maze_visited[n_y][n_x] = mv_cur
                        queue.appendleft((n_y, n_x))
        for i in range(-2, 3):
            for j in range(-2, 3):
                if abs(i) + abs(j) <= 1:
                    continue
                n_x, n_y = x + i, y + j
                if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                    mv_n = maze_visited[n_y][n_x]
                    if mv_n > mv_cur + 1:
                        if S[n_y][n_x] == '.':
                            maze_visited[n_y][n_x] = mv_cur + 1
                            queue.append((n_y, n_x))
    
H, W = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))
 
S = [list(input()) for i in range(H)]
 
maze_visited = [[math.inf] * W for i in range(H)]
 
explore(C,D)
 
if maze_visited[D[0] - 1][D[1] - 1] == math.inf:
    print('-1')
else:
    print(maze_visited[D[0] - 1][D[1] - 1])

Solution (Python):
import os
import sys

import numpy as np
from heapq import heappop, heappush


def solve(h, w, s, t, field):
    WARP = (-(w * 2 + 10), -(w * 2 + 9), -(w * 2 + 8), -(w * 2 + 7), -(w * 2 + 6),
            -(w + 6), -(w + 5), -(w + 3), -(w + 2),
            -2, 2,
            w + 2, w + 3, w + 5, w + 6,
            w * 2 + 6, w * 2 + 7, w * 2 + 8, w * 2 + 9, w * 2 + 10)
    WALK = (-(w + 4), -1, 1, w + 4)

    q = [(0, s)]
    visited = np.zeros((h + 4) * (w + 4), np.int8)
    while q:
        cost, v = heappop(q)
        if v == t:
            return cost
        if visited[v]:
            continue
        visited[v] = 1
        for d in WALK:
            if field[v + d] or visited[v + d]:
                continue
            heappush(q, (cost, d + v))
        for d in WARP:
            if field[v + d] or visited[v + d]:
                continue
            heappush(q, (cost + 1, d + v))

    return -1


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8,i8,i8,i8,i1[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8,i8,i8,i8,i1[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

h, w = map(int, sys.stdin.readline().split())
ch, cw = map(int, sys.stdin.readline().split())
dh, dw = map(int, sys.stdin.readline().split())
field = np.ones((h + 4) * (w + 4), dtype=np.int8)
for i in range(h):
    line = sys.stdin.readline().strip()
    field[(i + 2) * (w + 4) + 2:(i + 2) * (w + 4) + w + 2] = list(map('.
s = (ch + 1) * (w + 4) + cw + 1
t = (dh + 1) * (w + 4) + dw + 1
ans = solve(h, w, s, t, field)
print(ans)

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,Cw=Ch-1,Cw-1
Dh,Dw=Dh-1,Dw-1
from collections import deque
todo=deque([[0,Ch,Cw]])
d=[[-1]*w for _ in range(h)]
d[Ch][Cw]=0
toho=[[0,1],[0,-1],[1,0],[-1,0]]
wiz=[[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 todo:
  cnt,nh,nw=todo.popleft()
  if d[nh][nw]<cnt:continue
  for dh,dw in toho:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt:
        d[nh+dh][nw+dw]=cnt
        todo.appendleft([cnt,nh+dh,nw+dw])
  for dh,dw in wiz:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt+1:
        d[nh+dh][nw+dw]=cnt+1
        todo.append([cnt+1,nh+dh,nw+dw])
print(d[Dh][Dw])

Solution (Python):
from collections import deque
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
maze=[]

for i in range(H):
  l=list(input())
  for j in range(len(l)):
    if l[j]=='.':l[j]=-1
    if l[j]=='
  maze.append(l)

def isIn(h,w):
  if h<0 or h>=H or w<0 or w >=W:return False
  return True
l=[[Ch-1,Cw-1]]
l=deque(l)
maze[Ch-1][Cw-1]=0
l2=[[0]*W for i in range(H)]

cnt=0
while l:
  cnt+=1
  vectors=[[-1,0],[1,0],[0,1],[0,-1]]

  target=l[0]
  h,w=target
  l.popleft()
  if l2[h][w]:
    continue
  l2[h][w]=1
  for vector in vectors:
    if not isIn(h+vector[0],w+vector[1]):continue
    if maze[h+vector[0]][w+vector[1]]>maze[h][w] or maze[h+vector[0]][w+vector[1]]==-1:
      maze[h+vector[0]][w+vector[1]]=maze[h][w]
      l.appendleft([h+vector[0],w+vector[1]])
  for i in range(25):
    if not isIn(h+i//5-2,w+i%5-2):continue
    if maze[h+i//5-2][w+i%5-2]>maze[h][w] or maze[h+i//5-2][w+i%5-2]==-1:
      maze[h+i//5-2][w+i%5-2]=maze[h][w]+1
      l.append([h+i//5-2,w+i%5-2])
print(maze[Dh-1][Dw-1])

Solution (Python):

import sys
def _p(*_a):
  
  _s=" ".join(map(str,_a))
  
  sys.stderr.write(_s+"\n")

def _pa(_aa):
  
  for _a in _aa: _p(_a)

H,W = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
M = list( list(input()) for _ in range(H) )





INF = 10**18

for h in range(H):
  for w in range(W):
    if M[h][w] == ".": M[h][w] = INF
    

ch -= 1
cw -= 1
dh -= 1
dw -= 1

M[ch][cw] = 0





from collections import deque
Q = deque()
Q.append((ch,cw))

ans = INF

while Q:
  h,w = Q.popleft()

  for ih,iw in [(1,0), (-1,0), (0,1), (0,-1)]:
    nh = h + ih
    nw = w + iw
    if nh < 0 or H <= nh: continue
    if nw < 0 or W <= nw: continue
    if M[nh][nw] == "

    if nh == dh and nw == dw:
      M[nh][nw] = min(M[h][w], M[dh][dw])
      ans = min(ans, M[nh][nw])
      continue

    if M[h][w] < M[nh][nw]:
      M[nh][nw] = M[h][w]
      Q.appendleft((nh,nw))
      continue

    if M[h][w] > M[nh][nw]:
      M[h][w] = M[nh][nw]
      Q.appendleft((h,w))

  for ih,iw in [(1,1), (1,-1), (-1,1), (-1,-1), (2,0), (2,1), (2,2), (2,-1), (2,-2), (1,2), (1,-2), (0,2), (0,-2), (-1,2), (-1,-2), (-2,0), (-2,1), (-2,-2), (-2,-1), (-2,-2)]:
    nh = h + ih
    nw = w + iw
    if nh < 0 or H <= nh: continue
    if nw < 0 or W <= nw: continue
    if M[nh][nw] == "

    if nh == dh and nw == dw:
      M[nh][nw] = min(M[h][w]+1, M[dh][dw])
      ans = min(ans, M[nh][nw])
      continue

    if M[h][w]+1 < M[nh][nw]:
      M[nh][nw] = M[h][w]+1
      Q.append((nh,nw))
      continue

    if M[h][w] > M[nh][nw]+1:
      M[h][w] = M[nh][nw]+1
      Q.append((h,w))



if ans == INF: ans = -1
print(ans)

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)
    
    


    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


    
    targets = deque([(Ch,Cw,0)])
    while targets:
        y,x,d = targets.pop()
        if not check_and_move(y,x,d):
            continue

        if y == Dh and x == Dw:
            break

        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
def _p(*_a):
  
  _s=" ".join(map(str,_a))
  
  sys.stderr.write(_s+"\n")

def _pa(_aa):
  
  for _a in _aa: _p(_a)

H,W = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
M = list( list(input()) for _ in range(H) )

if ch==dh and cw==dw:
  print(0)
  exit()

INF = 10**18

for h in range(H):
  for w in range(W):
    if M[h][w] == ".": M[h][w] = INF
    

ch -= 1
cw -= 1
dh -= 1
dw -= 1

M[ch][cw] = 0





from collections import deque
Q = deque()
Q.append((ch,cw))

ans = INF

while Q:
  h,w = Q.popleft()

  for ih,iw in [(1,0), (-1,0), (0,1), (0,-1)]:
    nh = h + ih
    nw = w + iw
    if nh < 0 or H <= nh: continue
    if nw < 0 or W <= nw: continue
    if M[nh][nw] == "

    if nh == dh and nw == dw:
      M[nh][nw] = min(M[h][w], M[dh][dw])
      ans = min(ans, M[nh][nw])
      continue

    if M[h][w] < M[nh][nw]:
      M[nh][nw] = M[h][w]
      Q.appendleft((nh,nw))
      continue

    if M[h][w] > M[nh][nw]:
      M[h][w] = M[nh][nw]
      Q.appendleft((h,w))

  for ih,iw in [(1,1), (1,-1), (-1,1), (-1,-1), (2,0), (2,1), (2,2), (2,-1), (2,-2), (1,2), (1,-2), (0,2), (0,-2), (-1,2), (-1,-2), (-2,0), (-2,1), (-2,-2), (-2,-1), (-2,-2)]:
    nh = h + ih
    nw = w + iw
    if nh < 0 or H <= nh: continue
    if nw < 0 or W <= nw: continue
    if M[nh][nw] == "

    if nh == dh and nw == dw:
      M[nh][nw] = min(M[h][w]+1, M[dh][dw])
      ans = min(ans, M[nh][nw])
      continue

    if M[h][w]+1 < M[nh][nw]:
      M[nh][nw] = M[h][w]+1
      Q.append((nh,nw))
      continue

    if M[h][w] > M[nh][nw]+1:
      M[h][w] = M[nh][nw]+1
      Q.append((h,w))



if ans == INF: ans = -1
print(ans)

Solution (Python):
import copy
import math
import time
import statistics
import math
import itertools
import bisect
import sys
from decimal import *
from collections import deque


def get_int():
    return int(input())

def get_string():
    return input()

def get_int_list():
    return [int(x) for x in input().split()]

def get_string_list():
    return input().split()

def get_int_multi():
    return map(int, input().split())

def get_string_char_list():
    return list(str(input()))



sys.setrecursionlimit(10 ** 6)

def main():
    start = time.time()

    h, w = get_int_list()
    sr, sc = get_int_list()
    er, ec = get_int_list()

    d = [[-1] * (w+2) for _ in range(h+2)]

    for i in range(h):
        wk = get_string()
        for ii in range(w):
            if wk[ii] == ".":
                d[i+1][ii+1] = 10 ** 6

    d[sr][sc] = 0
    q = deque([])
    q2 = deque([])
    q.append([sr,sc])
    q2.append([sr,sc])

    def idou(i,ii,cnt_mahou):
        if 1 <= i <= h and 1 <= ii <= w:
            if d[i][ii] == 10 ** 6:
                q.append([i, ii])
                d[i][ii] = cnt_mahou


    ans = -1
    flg = True
    finish = False
    while flg:
        flg = False
        while q:
            wk = q.popleft()
            q2.append(wk)

            i = wk[0]
            ii = wk[1]
            cnt_mahou = d[i][ii]

            idou(i - 1, ii, cnt_mahou)
            idou(i + 1, ii, cnt_mahou)
            idou(i, ii - 1, cnt_mahou)
            idou(i, ii + 1, cnt_mahou)

            if d[er][ec] != 10 ** 6:
                ans = d[er][ec]
                finish = True
                break

        if finish:
            break

        while q2:
            wk = q2.popleft()
            i = wk[0]
            ii = wk[1]
            
            for wk in range(-2, 3):
                for wk2 in range(-2, 3):
                    if abs(wk) + abs(wk2) > 1:
                        flg = True
                        idou(i + wk, ii + wk2, cnt_mahou + 1)

    print(ans)

    


if __name__ == '__main__':
    main()

Solution (Python):


import sys
import pprint
from collections import deque


sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	h, w = map(int, sys.stdin.readline().split())
	ch, cw = map(int, sys.stdin.readline().split())
	dh, dw = map(int, sys.stdin.readline().split())
	s = [sys.stdin.readline().rstrip() for i in [0]*h]
	graph = [[[] for i in [0]*w] for j in [0]*h]
	
	def getMaze(x, y):
		if not (0 <= x < w and 0 <= y < h):
			return -1
		return s[y][x]

	for y in range(h):
		for x in range(w):
			if s[y][x] == "
				continue
			


	
	stack = deque([(cw-1, ch-1)])
	dist = [[float("inf")]*w for i in range(h)]
	while len(stack) != 0:
		x, y = stack.popleft()
		log.print(x, y, dist[y][x])
		if dist[y][x] == float("inf"):
			dist[y][x] = 0
		d = dist[y][x]
		nexts = []
		for i in range(-2, 2+1):
			for j in range(-2, 2+1):
				if (i, j) == (0, 0):
					continue
				if getMaze(x + i, y + j) == ".":
					if (i, j) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
						nexts.append((x + i, y + j, 0))
					else:
						nexts.append((x + i, y + j, 1))
		for next in nexts:
			nx, ny, cost = next
			if dist[ny][nx] > d + cost:
				dist[ny][nx] = d + cost
				if cost == 1:
					stack.append((nx, ny))
				else:
					stack.appendleft((nx, ny))
	log.print(dist)
	if dist[dh-1][dw-1] == float("inf"):
		print(-1)
	else:
		print(dist[dh-1][dw-1])
	
	


main()

Solution (Python):
from collections import deque
H, W = map(int, input().split())  
CY, CX = map(lambda x: int(x)-1, input().split())  
DY, DX = map(lambda x: int(x)-1, input().split())  
gridgraph = [input() for _ in range(H)]


q = deque()
q.append((CY, CX))  

adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]  
distant = [[10**10]*W for _ in range(H)]
distant[CY][CX] = 0
warp_y = list(range(-2, 3, 1))
warp_x = list(range(-2, 3, 1))
while len(q):
    cy, cx = q.popleft()  
    for dy, dx in adjacent:
        
        ny = cy+dy
        nx = cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        
        if gridgraph[ny][nx] == "." and distant[ny][nx] > distant[cy][cx]:
            
            distant[ny][nx] = distant[cy][cx]
            q.appendleft((ny, nx))
    
    for i in warp_y:
        for j in warp_x:
            target_y, target_x = cy+i, cx+j
            if target_y < 0 or target_y >= H or target_x < 0 or target_x >= W:
                continue
            else:
                if gridgraph[target_y][target_x] == "." and distant[target_y][target_x] > distant[cy][cx]+1:
                    distant[target_y][target_x] = distant[cy][cx]+1
                    q.append((target_y, target_x))

if distant[DY][DX] == 10**10:
    print(-1)
else:
    print(distant[DY][DX])

Solution (Python):

import sys
def _p(*_a):
  
  _s=" ".join(map(str,_a))
  
  sys.stderr.write(_s+"\n")

def _pa(_aa):
  
  for _a in _aa: _p(_a)

H,W = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
M = list( list(input()) for _ in range(H) )

if ch==dh and cw==dw:
  print(0)
  exit()

INF = 10**18

for h in range(H):
  for w in range(W):
    if M[h][w] == ".": M[h][w] = INF
    

ch -= 1
cw -= 1
dh -= 1
dw -= 1

M[ch][cw] = 0





from collections import deque
Q = deque()
Q.append((ch,cw))

ans = INF

while Q:
  h,w = Q.popleft()

  for ih,iw in [(1,0), (-1,0), (0,1), (0,-1)]:
    nh = h + ih
    nw = w + iw
    if nh < 0 or H <= nh: continue
    if nw < 0 or W <= nw: continue
    if M[nh][nw] == "

    if nh == dh and nw == dw:
      M[nh][nw] = min(M[h][w], M[dh][dw])
      ans = min(ans, M[nh][nw])
      continue

    if M[h][w] < M[nh][nw]:
      M[nh][nw] = M[h][w]
      Q.appendleft((nh,nw))
      continue

    if M[h][w] > M[nh][nw]:
      M[h][w] = M[nh][nw]
      Q.appendleft((h,w))

  for ih,iw in [(1,1), (1,-1), (-1,1), (-1,-1), (2,0), (2,1), (2,2), (2,-1), (2,-2), (1,2), (1,-2), (0,2), (0,-2), (-1,2), (-1,-2), (-2,0), (-2,1), (-2,-2), (-2,-1), (-2,-2)]:
    nh = h + ih
    nw = w + iw
    if nh < 0 or H <= nh: continue
    if nw < 0 or W <= nw: continue
    if M[nh][nw] == "

    if nh == dh and nw == dw:
      M[nh][nw] = min(M[h][w]+1, M[dh][dw])
      ans = min(ans, M[nh][nw])
      continue

    if M[h][w]+1 < M[nh][nw]:
      M[nh][nw] = M[h][w]+1
      Q.append((nh,nw))
      continue

    if M[h][w] > M[nh][nw]+1:
      M[h][w] = M[nh][nw]+1
      Q.append((h,w))



if ans == INF: ans = -1
print(ans)

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):
from collections import deque
H, W = map(int, input().split())
C_1, C_2 = map(int, input().split())
D_1, D_2 = map(int, input().split())
T = []
for i in range(H):
    A = list(input())
    T.append(A)
used = [[0]*W for _ in range(H)]
P = deque([(C_1 - 1, C_2 - 1, 0)])
while(True):
    if len(P) == 0:
        print(-1)
        break
    a, b, cost = P.popleft()
    if (a, b) == (D_1 - 1, D_2 - 1):
        print(cost)
        break
    if used[a][b] == 0:
        used[a][b] = 1
        for i, j in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            if 0 <= a + i <= H-1:
                if 0 <= b + j <= W-1:
                    if T[a+i][b+j] == ".":
                        P.appendleft((a + i, b + j, cost))
        for i in range(-2, 3):
            for j in range(-2, 3):
                if 0 <= a + i <= H-1:
                    if 0 <= b + j <= W-1:
                        if T[a+i][b+j] == ".":
                            P.append((a + i, b + j, cost + 1))

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr



def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

h,w = lr()
ch,cw = lr()
ch-=1
cw-=1
dh, dw = lr()
dh-=1
dw-=1
s = [input() for i in range(h)]
visited = [[inf for j in range(w)] for i in range(h)]
visited[ch][cw] = 0
q = deque([[ch, cw]])
dq = deque([[ch, cw]])
dir = [[0,1], [0,-1], [-1,0], [1,0]]
while q:
    y,x = q.popleft()
    c = visited[y][x]
    for dy,dx in dir:
        ny,nx = y+dy,x+dx
        if 0<=ny<h and 0<=nx<w:
            if s[ny][nx] == '.':
                if visited[ny][nx] > c:
                    visited[ny][nx] = c
                    q.append([ny,nx])
                    dq.append([ny,nx])
    if len(q) == 0:
        
        tmp = []
        while dq:
            ry,rx = dq.popleft()
            ty,tx = ry-2, rx-2
            for i in range(5):
                for j in range(5):
                    ny, nx = ty+i, tx+j
                    if 0<=ny<h and 0<=nx<w:
                        if s[ny][nx]=='.':
                            if visited[ny][nx] > c+1:
                                visited[ny][nx] = c+1
                                q.append([ny,nx])
                                tmp.append([ny,nx])
        dq = deque(tmp)
if visited[dh][dw] != inf:
    print(visited[dh][dw])
else:
    print(-1)