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

Solution (Python):
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    CH, CW = [int(x) - 1 for x in input().split()]
    DH, DW = [int(x) - 1 for x in input().split()]
    S = [input().strip() for _ in range(H)]

    warp = [[-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]]

    visited = [[float("inf")] * W for _ in range(H)]

    q = collections.deque()
    visited[CH][CW] = 0
    q.append((CH, CW))
    while q:
        cx, cy = q.popleft()
        cc = visited[cx][cy]

        
        kabe_cnt = 0
        for nx, ny in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            nnx = cx + nx
            nny = cy + ny
            if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                if S[nnx][nny] == ".":
                    if visited[nnx][nny] > cc:
                        q.appendleft((nnx, nny))
                        visited[nnx][nny] = cc
                else:
                    kabe_cnt += 1

        
        if kabe_cnt > 0:
            for nx, ny in warp:
                nnx = cx + nx
                nny = cy + ny
                if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                    if S[nnx][nny] == "." and visited[nnx][nny] > cc + 1:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc + 1

    if visited[DH][DW] == float("inf"):
        print(-1)
    else:
        print(visited[DH][DW])


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys

def func(s, array, i, x, y):
  if x < 0 or y < 0 or x >= len(array) or y >= len(array[x]):
    return
  
  if s[x][y] == '
    return
  
  array[x][y] = i
  func(s, array, index, x+1, y)
  func(s, array, index, x, y+1)
  func(s, array, index, x-1, y)
  func(s, array, index, x, y-1)
  

h,w = map(int,input().split())
c1,c2 = map(int,input().split())
d1,d2 = map(int,input().split())

s = []

for i in range(h):
  s.append(input())
  
array = [[0 for i in range(w)] for i in range(h)]
index = 1
for i in range(len(array)):
  for j in range(len(array[i])):
    if s[i][j] == '.' and array[i][j] == 0:
      func(s, array, index, i, j)
      index += 1

setArray = [set() for i in range(index)]
for i in range(len(array)):
  for j in range(len(array[i])):
    for k in range(max(i-2, 0), min(i+3, len(array))):
      for l in range(max(j-2, 0), min(j+3, len(array[0]))):
        if array[k][l] != 0:
          setArray[array[i][j]].add(array[k][l])

start = array[c1-1][c2-1]
end = array[d1-1][d2-1]

if start == end:
  print(0)
  sys.exit()

deq = deque()
array2 = [True] * index
for v in setArray[start]:
  if array2[v]:
    deq.append((1, v))
    array2[v] = False

while len(deq) != 0:
  tap = deq.popleft()
  if tap[1] == end:
    print(tap[0])
    sys.exit()
    
  for v in setArray[tap[1]]:
    if array2[v]:
      deq.append((tap[0]+1, v))
      array2[v] = False
      
print(-1)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    


class UnionFind:
    def __init__(self, N):
        self.N = N  
        self.n_groups = N  
        
        self.parent = [-1] * N  

    def root(self, A):
        
        
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])  
        return self.parent[A]

    def size(self, A):
        
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        
        
        A = self.root(A)
        B = self.root(B)

        
        if (A == B):
            return False

        
        if (self.size(A) < self.size(B)):
            A, B = B, A

        
        self.parent[A] += self.parent[B]  
        self.parent[B] = A  
        self.n_groups -= 1

        return True

    def is_in_same(self, A, B):
        return self.root(A) == self.root(B)


def read_map_as(H, replace={'
    '''
    文字列のmapを置換して読み込み。デフォでは
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            
            
    else:  
        ret = [[pad] * (W + 2)]  
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  
from functools import reduce
from math import gcd


def lcm(a, b):
    
    g = gcd(a, b)
    return a // g * b






H, W = ints()
si, sj = mina(*ints())
ti, tj = mina(*ints())
S = read_map_as(H)
uf = UnionFind(H * W)


def to_node(i, j): return i * W + j


def to_idx(node): return node // W, node % W


for i, j in product(range(H), range(W)):
    ij = i * W + j
    if S[i][j] == 1:
        continue
    for di, dj in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        ni, nj = i + di, j + dj
        if not (0 <= ni < H and 0 <= nj < W) or S[ni][nj] == 1:
            continue
        uf.unite(ij, ni * W + nj)


graph = defaultdict(lambda: set())
for i, j in product(range(H), range(W)):
    if S[i][j] == 1:
        continue
    thisnode = to_node(i, j)
    for di, dj in product([-2, -1, 0, 1, 2], repeat=2):
        ni = i + di
        nj = j + dj
        if di == dj == 0 or not(0 <= ni < H and 0 <= nj < W) or S[ni][nj] == 1:
            continue
        adj_node = to_node(ni, nj)
        if uf.is_in_same(thisnode, adj_node):
            continue
        a = uf.root(adj_node)
        b = uf.root(thisnode)
        graph[a].add(b)
        graph[b].add(a)



s_node = uf.root(to_node(si, sj))
t_node = uf.root(to_node(ti, tj))

que = deque([(s_node, 0)])
is_visited = [False] * len(uf.parent)

while que:
    u, c = que.popleft()
    if u == t_node:
        exit(c)
    for nx in graph[u]:
        if is_visited[nx]:
            continue
        que.append((nx, c + 1))
        is_visited[nx] = True
print(-1)

Solution (Python):
import sys
from collections import deque

def solve():
    readline = sys.stdin.readline

    H, W = map(int, readline().split())
    a, b = map(int, readline().split())
    c, d = map(int, readline().split())
    S = [readline().rstrip() for i in range(H)]

    a,b,c,d = (v - 1 for v in (a,b,c,d))

    INF = 10 ** 10

    groups = []

    visited = [[False] * W for i in range(H)]

    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    def dfs(x, y, group):
        if not (0 <= x < H and 0 <= y < W):
            return
        
        if visited[x][y]:
            return
        
        if S[x][y] == '
            return
        
        group.append((x,y))
        visited[x][y] = True

        for dx, dy in dirs:
            dfs(x + dx, y + dy, group)

    for i in range(H):
        for j in range(W):
            if S[i][j] == '.' and not visited[i][j]:
                group = []
                dfs(i, j, group)
                groups.append(group)
    
    
    p2g = [[-1] * W for i in range(H)]
    for i,group in enumerate(groups):
        for x,y in group:
            p2g[x][y] = i
    
    G = len(groups)
    g_adj = [set() for i in range(G)]
    for i in range(H):
        for j in range(W):
            src = p2g[i][j]
            if src == -1:
                continue
            for x in range(max(0, i - 2), min(H - 1, i + 2) + 1):
                for y in range(max(0, j - 2), min(W - 1, j + 2) + 1):
                    if x == i and y == j:
                        continue
                    if p2g[x][y] == -1:
                        continue
                    g_adj[src].add(p2g[x][y])
    
    
    src_g = p2g[a][b]
    dst_g = p2g[c][d]

    visited = [False] * G
    q = deque()
    q.append((src_g, 0))

    while q:
        node, depth = q.popleft()

        if node == dst_g:
            print(depth)
            return

        for adj in g_adj[node]:
            if not visited[adj]:
                visited[adj] = True
                q.append((adj, depth + 1))
    
    print(-1)

solve()

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

sy,sx=ch-1,hw-1
gx,gy=dw-1,dh-1

l = [None]*h
for i in range(h):
    l[i] = list(input())

dist = [[-1]*w for i in range(h)]
dist[sy][sx] = 0

from collections import deque
def walk(warped,cnt):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    Q = deque(warped)
    walked=warped
    changed=False
    while Q:
        p = Q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < w and 0 <= ny < h:
                if l[ny][nx]=="." and dist[ny][nx]==-1:
                    changed=True
                    Q.append([nx, ny])
                    walked.append([nx,ny])
                    dist[ny][nx] = cnt
                    if nx==gx and ny==gy:
                        print(cnt)
                        exit()
    return walked,changed
def warp(walked,cnt):
    warped=[]
    changed=False

    for x,y in walked:
        for dx in [-2,-1,0,1,2]:
            for dy in [-2,-1,0,1,2]:
                if abs(dx)+abs(dy)<=1:
                    continue

                nx=x+dx
                ny=y+dy
                if 0 <= nx < w and 0 <= ny < h:
                    if l[ny][nx]=="." and dist[ny][nx]==-1:
                        changed=True
                        warped.append([nx,ny])
                        dist[ny][nx] = cnt
                        if nx==gx and ny==gy:
                            print(cnt)
                            exit()
    return warped,changed

cnt=0

warped=[[sx,sy]]

while True:
    walked,walkchange= walk(warped,cnt)
    cnt+=1
    warped,warpchange=warp(walked,cnt)
    if not walkchange and not warpchange:
        print(-1)
        exit()

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

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

mtx = [[10 ** 9]*w for _ in range(h)]

cnt = -1
now = deque()
nxt = deque()
nxt.append((ch, cw))
mtx[ch][cw] = 0

while True:
    flag = False
    if not now:
        now = nxt
        cnt += 1
        nxt = deque()
        if not now:
            break
    h_ptr, w_ptr = now.pop()
    if h_ptr != 0:
        if s[h_ptr-1][w_ptr] == '.':
            if cnt < mtx[h_ptr-1][w_ptr]:
                mtx[h_ptr-1][w_ptr] = cnt
                now.append((h_ptr-1, w_ptr))
    if w_ptr != 0:
        if s[h_ptr][w_ptr-1] == '.':
            if cnt < mtx[h_ptr][w_ptr-1]:
                mtx[h_ptr][w_ptr-1] = cnt
                now.append((h_ptr, w_ptr-1))
    if h_ptr != h-1:
        if s[h_ptr+1][w_ptr] == '.':
            if cnt < mtx[h_ptr+1][w_ptr]:
                mtx[h_ptr+1][w_ptr] = cnt
                now.append((h_ptr+1, w_ptr))
    if w_ptr != w-1:
        if s[h_ptr][w_ptr+1] == '.':
            if cnt < mtx[h_ptr][w_ptr+1]:
                mtx[h_ptr][w_ptr+1] = cnt
                now.append((h_ptr, w_ptr+1))
    for i in range(h_ptr-2, h_ptr+3):
        for j in range(w_ptr-2, w_ptr+3):
            if 0 <= i < h and 0 <= j < w and s[i][j] == '.':
                if cnt + 1 < mtx[i][j]:
                    mtx[i][j] = cnt + 1
                    nxt.append((i, j))

ret = mtx[dh][dw]

if ret == 10 ** 9:
    print(-1)
else:
    print(ret)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
ch, cw = ch-1, cw-1
dh, dw = map(int, input().split())
dh, dw = 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 = [0,1,0,-1]
        dy = [1,0,-1,0]
        for i in range(4):
            ny = y+dy[i]
            nx = 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] = cnt[0]
            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
cnt = [0]
wp = deque([])
ok = False

while dq:
    while dq:
        y, x = dq.popleft()
        bfs(y, x)
        wp.append([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 = y+dy
                nx = x+dx
                if ny < 0 or ny >= h or nx < 0 or nx >= w: continue
                if s[ny][nx] == '
                if seen[ny][nx] == -1:
                    ok = True
                    seen[ny][nx] = (cnt[0]+1)
                    dq.append([ny, nx])
    if ok:
        cnt[0] += 1

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

Solution (Python):
import sys
from collections import deque
H, W = map(int, input().split())
sh, sw = map(int, input().split())
sh -= 1
sw -= 1
gh, gw = map(int, input().split())
gh -= 1
gw -= 1

C = []
for i in range(H):
    C.append(list(input()))

d = deque()
kabe = deque()
d.append([sh, sw])
looked = [[0 for i in range(W)]for j in range(H)]
looked[sh][sw] = 1
ans = 0
dx_dy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
kabe.append([sh, sw])
while d:
    x = d.pop()
    lookx = x[0]
    looky = x[1]
    for i in dx_dy:
        a = lookx+i[0]
        b = looky+i[1]
        if not(0 <= a < H) or not(0 <= b < W) or looked[a][b] == 1:
            continue
        if C[a][b] == "
            kabe.append([lookx, looky])
            continue
        if a == gh and b == gw:
            print(ans)
            sys.exit()
        d.append([a, b])
        looked[a][b] = 1

    if len(d) == 0:
        ans += 1
        ok = 0
        for _ in range(len(kabe)):
            kx, ky = kabe.pop()
            wapuxm = max(kx-2, 0)
            wapuxM = min(kx+2, H-1)
            wapuym = max(ky-2, 0)
            wapuyM = min(ky+2, W-1)
            for ki in range(wapuxm, wapuxM+1):
                for kj in range(wapuym, wapuyM+1):
                    if C[ki][kj] == "
                        continue
                    if C[ki][kj] == ".":
                        d.append([ki, kj])
                        looked[ki][kj] = 1
                        ok = 1
                    if ki == gh and kj == gw:
                        print(ans)
                        sys.exit()
        if ok == 0:
            print(-1)
            sys.exit()

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  H,W=LI()
  Ch,Cw=LI()
  Dh,Dw=LI()
  Ch-=1
  Cw-=1
  Dh-=1
  Dw-=1
  field=[S() for _ in range(H)]

  q=collections.deque()
  q2=collections.deque()
  q.append((Ch,Cw,0))
  ans=[[inf]*W for _ in range(H)]
  while True:
    if not q:
      if not q2:
        break
      else:
        q=q2
        q2=collections.deque()
    
    
    
    y,x,cnt=q.popleft()
    if ans[y][x]<=cnt:
      continue
    ans[y][x]=cnt
    if y==Dh and x==Dw:
      continue

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny<H and 0<=nx<W:
        if field[ny][nx]=='.':
          q.append((ny,nx,cnt))
        else:
          if dy==1 and dx==0:
            for i in range(0,2):
              for j in range(-2,3):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    if ans[nny][nnx]>cnt+1:
                      q2.append((nny,nnx,cnt+1))
          elif dy==0 and dx==1:
            for i in range(-2,3):
              for j in range(0,2):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    if ans[nny][nnx]>cnt+1:
                      q2.append((nny,nnx,cnt+1))
          elif dy==-1 and dx==0:
            for i in range(-1,1):
              for j in range(-2,3):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    if ans[nny][nnx]>cnt+1:
                      q2.append((nny,nnx,cnt+1))
          elif dy==0 and dx==-1:
            for i in range(-2,3):
              for j in range(-1,1):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    if ans[nny][nnx]>cnt+1:
                      q2.append((nny,nnx,cnt+1))

  x=ans[Dh][Dw]
  if x==inf:
    return -1
  return x


print(main())

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 = [list(input()) for i in range(H)]
visited = [[-1] * W for j in range(H)]

d = deque([[Ch - 1, Cw - 1]])
wq = deque([[Ch - 1, Cw - 1]])

visited[Ch - 1][Cw - 1] = 0
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
warp_move = [[-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]
             ]
warp = 0

while len(d) > 0 or len(wq) > 0:
    while len(d) > 0:
        y, x = d.popleft()
        wq.append([y, x])
        for i, j in move:
            nexty, nextx = y + i, x + j
            if nexty == Dh - 1 and nextx == Dw - 1:
                print(warp)
                exit()
            if nextx >= 0 and nextx < W and nexty >= 0 and nexty < H:
                if S[nexty][nextx] == "." and visited[nexty][nextx] == -1:
                    visited[nexty][nextx] = warp
                    d.append([nexty, nextx])

    warp += 1
    while len(wq) > 0:
        y, x = wq.popleft()
        for i, j in warp_move:
            warp_y, warp_x = y + i, x + j
            if warp_y == Dh - 1 and warp_x == Dw - 1:
                print(warp)
                exit()
            if warp_x >= 0 and warp_x < W and warp_y >= 0 and warp_y < H:
                if S[warp_y][warp_x] == "." and visited[warp_y][warp_x] == -1:
                    visited[warp_y][warp_x] = warp
                    d.append([warp_y, warp_x])
print(-1)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
start = list(map(int, input().split()))
goal = list(map(int, input().split()))
L = [list(input()) for _ in range(H)]
result = {}
def part(x, y, i, mem):
  if not (0<=x<H) or not (0<=y<W) or L[x][y]!=".":
    return
  L[x][y]=i
  mem.append((x,y))
  part(x-1, y, i, mem)
  part(x+1, y, i, mem)
  part(x, y-1, i, mem)
  part(x, y+1, i, mem)
mark = 0
for h in range(H):
  for w in range(W):
    if L[h][w]==".":
      mem = []
      part(h, w, mark, mem)
      result[mark]=mem
      mark += 1
dic = {i:-1 for i in range(mark)}
s = L[start[0]-1][start[1]-1]
dic[0]=0
g = L[goal[0]-1][goal[1]-1]
queue = deque([s])
while queue:
    now = queue.popleft()
    if now==g:
        print(dic[now])
        exit()
    for (x,y) in result[now]:
        for i in range(max(x-2, 0), min(x+3, H)):
            for j in range(max(y-2, 0), min(y+3, W)):
              key = L[i][j]
              if str(key)=="
                continue
              if dic[key] == -1:
                dic[key]= dic[now]+1
                queue.append(key)             
print("-1")

Solution (Python):
class Grid:
    def __init__(self, H, W, grid, road_wall=(".", "
        self.road, self.wall = road_wall
        self.H = H
        self.W = W
        self.grid = grid
        self.parent = [[-1] * self.W for _ in range(self.H)]
        self.move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     
        self.move2 = dict()
        self.move2 = [(-2, 0), (2, 1), (1, -2), (1, -1), (1, 2), (-2, 1), (-1, 1), (-2, -1), (-2, -2), (-1, -1), (-1, -2), (2, 2), (1, 1), (2, -1), (-1, 2), (-2, 2), (2, -2), (2, 0), (0, -2), (0, 2)]

    def bfs(self, start=(0,0), goal=-3, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if save:
            parent = self.parent
        else:
            parent = [[-1] * self.W for _ in range(self.H)]
        p, t = start, time
        parent[p[0]][p[1]] = -2
        next_set = deque([(p, t)])
        broken_set = deque([])
        while next_set:
            while next_set:
                p, t = next_set.popleft()
                h, w = p
                for dh, dw in self.move:
                    q = (h + dh, w + dw)
                    if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                        continue
                    if parent[q[0]][q[1]] != -1:
                        continue
                    if q == goal:
                        return t
                    parent[q[0]][q[1]] = p
                    if self.grid[q[0]][q[1]] == self.wall:         
                        for dh2, dw2 in self.move2:
                            r = (h + dh2, w + dw2)
                            broken_set.append((r, t))
                        continue
                    
                    
                    
                    next_set.append((q, t))
            while broken_set:
                q, t = broken_set.popleft()
                if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                    continue
                if parent[q[0]][q[1]] != -1:
                    continue
                if self.grid[q[0]][q[1]] == self.wall:  
                    continue
                if q == goal:
                    return t + 1
                
                
                
                next_set.append((q, t+1))
        return -1

    def debug(self, start, goal, p, t):
        player = p
        debug_grid = list(list(self.grid[h]) for h in range(self.H))
        if start != (None, None):
            debug_grid[start[0]][start[1]] = "S"
        if goal != -3:
            debug_grid[goal[0]][goal[1]] = "G"
        debug_grid[player[0]][player[1]] = "P"
        print("~~~~~~~~~ t = " + str(t + 1) + "  ~~~~~~~~")
        for debug_h in range(self.H):
            print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W)))




from collections import deque
import sys
input = sys.stdin.readline

road, wall = ".", "

H, W = map(int,input().split())                
x, y = map(int, input().split())
start = (x-1,y-1)
x, y = map(int, input().split())
goal = (x-1,y-1)
grid = []
for h in range(H):
    grid.append(input().rstrip())

g = Grid(H, W, grid, (road, wall))
res = g.bfs(start=start, goal=goal)
print(res)

"""
5 6
5 6
1 1
.




"""

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


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

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] 


dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = hpp(q)
    ux,uy = divmod(pu,w)
    
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):


        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] is None or seen[u]>num:
            seen[u] = num
            hp(q, (num, u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)

Solution (Python):
import sys
input = sys.stdin.readline
 
h,w = list(map(int,input().split()))
s1,s2 = list(map(int,input().split()))
f1,f2 = list(map(int,input().split()))
 
s1,s2 = s1-1,s2-1
f1,f2 = f1-1,f2-1
 
Q = [(s1,s2)]
V = [[0]*w for _ in range(h)]
G = []
ALL = [(s1,s2)]
V[s1][s2] = 1
 
for _ in range(h):
  tmp = list(input().rstrip())
  G.append(tmp)
 
count = 0
best = 0
 
while True:
  while Q:
    new_Q = []
    for node in Q:
      i,j = node[0], node[1]
      if V[i][j]==0:
        ALL.append((i,j))
        V[i][j] = 1

      if i-1>0:
        if V[i-1][j]==0 and G[i-1][j]=='.':
          V[i-1][j]=1
          new_Q.append((i-1,j))
          ALL.append((i-1,j))
 
      if j-1>0:
        if V[i][j-1]==0 and G[i][j-1]=='.':
          V[i][j-1]=1
          new_Q.append((i,j-1))
          ALL.append((i,j-1))
 
      if i+1<h:
        if V[i+1][j]==0 and G[i+1][j]=='.':
          V[i+1][j]=1
          new_Q.append((i+1,j))
          ALL.append((i+1,j))
 
      if j+1<w:
        if V[i][j+1]==0 and G[i][j+1]=='.':
          V[i][j+1]=1
          new_Q.append((i,j+1))
          ALL.append((i,j+1))
 
    Q = new_Q
 
  if V[f1][f2]==1:
    print(count)
    break
  else:
    count += 1
    part= []
    
    ALL = list(set(ALL))
 
    for node in ALL:
      i,j = node[0], node[1]
      
      for x in range(i-2,i+3):
        for y in range(j-2,j+3):
          if x>-1 and y>-1 and x<h and y<w and G[x][y] == '.' and V[x][y]==0:
            part.append((x,y))         	
       
    ALL = list(set(part))
    
    Q = list(ALL)
    
    if (f1,f2) in ALL:
      print(count)
      break
 
    if len(ALL)==0:
      print(-1)
      break
      
    ALL = []

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

from collections import deque, defaultdict




from copy import deepcopy

def grid_wall(grid, h, w, wall='
    G = [[wall]*(w+2) for _ in range(h+2)]
    for hi in range(h):
        G[hi+1][1:w+1] = grid[hi]
    return G

def solve():
    H, W = MI()
    ch, cw = MI()
    dh, dw = MI()
    G = LLS(H)
    GW = grid_wall(G, H, W)
    GW[dh][dw] = 'G'
    

    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    used = deepcopy(GW)
    used[ch][cw] = '
    d = deque([(0, ch, cw, used)])


    while d:
        
        tmp2 = []
        while d:
            m, h, w, u = d.popleft()

            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    nh, nw = dh+h, dw+w
                    if not 0 <= nh <= H or not 0 <= nw <= W:
                        continue
                    if u[nh][nw] == '
                        continue

                    if (dh, dw) in move:
                        
                        if u[nh][nw] == '
                            continue
                        elif u[nh][nw] == 'G':
                            print(m)
                            return
                        d.append((m, nh, nw, u))
                        u[nh][nw] = '
                        continue

                    if u[nh][nw] == '
                        continue
                    
                    
                    
                    tmp2.append((m+1, nh, nw))

        
        
        for mm, nh, nw in tmp2:
            if u[nh][nw] == '
                continue
            elif u[nh][nw] == 'G':
                print(mm)
                return
            u[nh][nw] = '
            d.append((mm, nh, nw, u))

    print(-1)

if __name__ == '__main__':
    solve()