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
import copy

input = sys.stdin.readline

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [input() for _ in range(h)]

v = [[-1] * w for _ in range(h)]
d = [(0,1), (0,-1), (1,0), (-1,0)]
d2 = [(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)]

v[ch-1][cw-1] = 0

q = deque([(ch-1, cw-1)])
q2 = [(ch-1, cw-1)]
tmp = 0

while True:
    while q:
        i,j = q.popleft()
        for ii,jj in d:
            if 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp
                    q.append((i+ii,j+jj))
                    q2.append((i+ii,j+jj))

    cnt = 0
    for k in range(len(q2)):
        i,j = q2[k][0], q2[k][1]
        for ii,jj in d2:
            if v[i][j] == tmp and 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp+1
                    q.append((i+ii,j+jj))
                    q2.append((i+ii,j+jj))
                    cnt += 1
    if not q:
        break
    tmp += 1
    q2 = q2[-cnt:]
print(v[dh-1][dw-1])

Solution (Python):
import collections

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

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

field = [[False for i in range(w)] for j in range(h)]
field[sy][sx] = True
dx = [1,0,-1,0]
dy = [0,1,0,-1]

q = collections.deque()
q2 = collections.deque()
q.append((sy,sx))
count = 0
maze[sy][sx] = 0

def f(count):
    while q:
        s = q.popleft()
        y,x = s[0],s[1]
        count = maze[y][x]
        for i in range(4):
            newy = y + dy[i]
            newx = x + dx[i]
            if 0<=newy<h and 0<=newx<w:
                if newy == gy and newx == gx:
                    print(count)
                    exit()
                if maze[newy][newx] == ".":
                    maze[newy][newx] = count
                    q.appendleft((newy,newx))
                elif maze[newy][newx] != "
                    maze[newy][newx] = count
                    q.appendleft((newy,newx))
                field[newy][newx] = True
        for ddy in range(-2,3):
            for ddx in range(-2,3):
                newy = y+ddy
                newx = x+ddx
                if  0<=newy<h and 0<=newx<w:
                    if maze[newy][newx] == "." and field[newy][newx] == False:
                        maze[newy][newx] = count+1
                        q.append((newy,newx))

f(count)
if maze[gy][gx] != ".":
    print(maze[gy][gx])
else:
    print(-1)

Solution (Python):
h,w = map(int,input().split())
c,d = map(int,input().split())
e,f = map(int,input().split())
s = []
t = []
m = h*w
for i in range(h):
    s.append(input())
    t.append([m]*w)
c -= 1
d -= 1
t[c][d] = 0
cnt = 0
stc1 = [[c,d]]
stc2 = []
a = 0
while(1):
    if(c > 0):
        if(s[c-1][d] == '.' and t[c-1][d] > cnt):
            t[c-1][d] = cnt
            stc1.append([c-1,d])
    if(d > 0):
        if(s[c][d-1] == '.' and t[c][d-1] > cnt):
            t[c][d-1] = cnt
            stc1.append([c,d-1])
    if(c < h-1):
        if(s[c+1][d] == '.' and t[c+1][d] > cnt):
            t[c+1][d] = cnt
            stc1.append([c+1,d])
    if(d < w-1):
        if(s[c][d+1] == '.' and t[c][d+1] > cnt):
            t[c][d+1] = cnt
            stc1.append([c,d+1])
    for j in range(-2,3):
        for k in range(-2,3):
            if(abs(j)+abs(k) > 1):
                if(c+j >= 0 and c+j < h and d+k >= 0 and d+k < w):
                    if(s[c+j][d+k] == '.' and t[c+j][d+k] > cnt+1):
                        t[c+j][d+k] = min(t[c+j][d+k],cnt+1)
                        stc2.append([c+j,d+k])
    if(len(stc1) > a+1):
        a += 1
        c = stc1[a][0]
        d = stc1[a][1]
    else:
        if(len(stc2) > 0):
            stc1 = stc2
            stc2 = []
            a = 0
            c = stc1[0][0]
            d = stc1[0][1]
            cnt += 1
        else:
            break
if(t[e-1][f-1] == m):
    print(-1)
else:
    print(t[e-1][f-1])

Solution (Python):
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
lh, lw = map(int, input().split())
tizu = [input() for _ in range(h)]

inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
lh -= 1
lw -= 1
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]

queue.append([ch, cw])
d = 0

while queue:
    queue2 = queue.copy()
    queue = deque()
    while queue2:
        pos = queue2.popleft()
        flg = [False, False, False, False]
        for dh, dw in walk:
            n_h = pos[0] + dh
            n_w = pos[1] + dw
            if n_h == -1 or n_w == -1 or n_h == h or n_w == w:
                continue
            if tizu[n_h][n_w] == "
                if dh == 1:
                    flg[0] = True
                elif dh == -1:
                    flg[1] = True
                elif dw == 1:
                    flg[2] = True
                else:
                    flg[3] = True
                continue
            if check[n_h][n_w] <= d:
                continue
            check[n_h][n_w] = d
            queue2.append([n_h, n_w])
            
        magic = []
        if flg[0]:
            magic.append([2, 0])
            if flg[2]:
                magic.append([2, 1])
                magic.append([2, 2])
                magic.append([1, 2])
                magic.append([1, 1])
            if flg[3]:
                magic.append([2, -1])
                magic.append([2, -2])
                magic.append([1, -2])
                magic.append([1, -1])
        if flg[1]:
            magic.append([-2, 0])
            if flg[2]:
                magic.append([-2, 1])
                magic.append([-2, 2])
                magic.append([-1, 2])
                magic.append([-1, 1])
            if flg[3]:
                magic.append([-2, -1])
                magic.append([-2, -2])
                magic.append([-1, -2])
                magic.append([-1, -1])
        if flg[2]:
            magic.append([0, 2])
        if flg[3]:
            magic.append([0, -2])
            
        for dh, dw in magic:
            n_h = pos[0] + dh
            n_w = pos[1] + dw
            if n_h == -1 or n_w == -1 or n_h == h or n_w == w:
                continue
            if tizu[n_h][n_w] == "
                continue
            if check[n_h][n_w] <= d + 1:
                continue
            check[n_h][n_w] = d + 1
            queue.append([n_h, n_w])
    d += 1

if check[lh][lw] == inf:
    print(-1)
else:
    print(check[lh][lw])

Solution (Python):
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
import copy


MOD = 10 ** 9 + 7




class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]


h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
A = [input() for i in range(h)]

tree = Uf(h*w)
for i in range(h):
    for j in range(w):
        if A[i][j] == "
            continue
        if i > 0 and A[i-1][j] == ".":
            tree.unite(w*i+j, w*(i-1)+j)
        if i < h-1 and A[i+1][j] == ".":
            tree.unite(w*i+j, w*(i+1)+j)
        if j > 0 and A[i][j-1] == ".":
            tree.unite(w*i+j, w*i+(j-1))
        if j < w-1 and A[i][j+1] == ".":
            tree.unite(w*i+j, w*i+(j+1))



par_list = set()
for i in range(h):
    for j in range(w):
        if A[i][j] == ".":
            par_list.add(tree.root(w*i+j))



node = dict()
for i, e in enumerate(par_list):
    node[e] = i



edge_list = set()
for i in range(h):
    for j in range(w):
        if A[i][j] == ".":
            for a in range(max(0, i - 2), min(h, i+3)):
                for b in range(max(0, j - 2), min(w, j + 3)):
                    if A[a][b] == "." and tree.root(w*i+j) != tree.root(w*a+b):
                        edge_list.add((node[tree.root(w*i+j)], node[tree.root(w*a+b)]))
                        edge_list.add((node[tree.root(w*a + b)], node[tree.root(w*i + j)]))

start = node[tree.root(w*(ch-1) + cw-1)]
goal = node[tree.root(w*(dh-1) + dw-1)]

g = [[] for i in range(len(node))]
for e in edge_list:
    g[e[0]].append(e[1])



que = deque([(start, 0)])
seen = set()
seen.add(start)
while que:
    cur, time = que.popleft()
    if cur == goal:
        print(time)
        exit()
    for nxt in g[cur]:
        if nxt not in seen:
            seen.add(nxt)
            que.append((nxt, time+1))

print(-1)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
cy, cx = map(lambda x:int(x)-1, input().split())
gy, gx = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(h)]
seen = [[-1]*w for _ in range(h)]
def f(sy, sx, cnt):
    que = []
    que.append((sy, sx))
    seen[sy][sx] = cnt
    while que:
        y, x = que.pop()
        for dy, dx in ((-1,0),(0,-1),(1,0),(0,1)):
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if seen[ny][nx] != -1:
                    continue
                if S[ny][nx] == "
                    continue
                seen[ny][nx] = cnt
                que.append((ny, nx))
cnt = 0
for i in range(h):
  for j in range(w):
    if S[i][j] == "." and seen[i][j] == -1:
      f(i, j, cnt)
      cnt += 1
G = [set() for _ in range(cnt+1)]
for i in range(h):
  for j in range(w):
    for dy in range(-2, 3):
      for dx in range(-2, 3):
        y, x = i+dy, j+dx
        if 0 <= y < h and 0 <= x < w:
          if S[i][j] == "
            continue
          if S[y][x] == "
            continue
          G[seen[i][j]].add(seen[y][x])
          G[seen[y][x]].add(seen[i][j])
s = seen[cy][cx]
g = seen[gy][gx]
dist = [-1]*(cnt+1)
dist[s] = 0
que = deque()
que.append(s)
while que:
  v = que.popleft()
  if g == v:
    print(dist[g])
    exit()
  for i in G[v]:
    if dist[i] != -1:
      continue
    dist[i] = dist[v]+1
    que.append(i)
print(-1)

Solution (Python):
h,w = list(map(int, input().split()))

ch,cw = list(map(int, input().split()))

dh,dw = list(map(int, input().split()))
b = [['
for _ in range(h):
    b.append(['
b.append(['

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

visit = [[False]*(w+2) for _ in range(h+2)]

warp = 0
while q or nq:
    while q:
        y,x = q.popleft()
        if (y,x) == (dh,dw):
            print(warp)
            exit()
        if visit[y][x]:
            continue
        visit[y][x] = True
        for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
            if b[y+dy][x+dx] == '.':
                if not visit[y+dy][x+dx]:
                    q.append((y+dy, x+dx))
            else:
                for dx in (-2,-1,0,1,2):
                    for dy in (-2,-1,0,1,2):
                        if y+dy > h or x + dx > w:
                            continue
                        if b[y+dy][x+dx] == '.':
                            if not visit[y+dy][x+dx]:
                                nq.append((y+dy, x+dx))
    q = nq
    nq = deque()
    warp += 1
    
print(-1)

Solution (Python):
import sys
import queue
import heapq


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

S = []
for _ in range(H):
    s = str(input())
    S.append(list(s))



q = []
heapq.heappush(q, (0, (Ch, Cw)))
fp = [[float('inf')] * W for _ in range(H)]
fp[Ch][Cw] = 0
while q:
    count, coo = heapq.heappop(q)
    uh, uw = coo

    if count > fp[uh][uw]:
        continue

    for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        vh = uh + dh
        vw = uw + dw

        
        if vh < 0 or vh >= H:
            continue
        if vw < 0 or vw >= W:
            continue

        
        if S[vh][vw] == "
            continue

        
        if fp[vh][vw] <= fp[uh][uw]:
            continue

        
        fp[vh][vw] = fp[uh][uw]
        heapq.heappush(q, (fp[vh][vw], (vh, vw)))

    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if (dh, dw) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                continue

            vh = uh + dh
            vw = uw + dw

            
            if vh < 0 or vh >= H:
                continue
            if vw < 0 or vw >= W:
                continue

            
            if S[vh][vw] == "
                continue

            
            if fp[vh][vw] <= fp[uh][uw] + 1:
                continue

            
            fp[vh][vw] = fp[uh][uw] + 1
            heapq.heappush(q, (fp[uh][uw] + 1, (vh, vw)))


if fp[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(fp[Dh][Dw])

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
C = LIST()
D = LIST()
S = [input() for i in range(H)]

visited = [[False] * W for i in range(H)]
dist = [[INF] * W for i in range(H)]
q = deque([(C[0]-1, C[1]-1)])

dist[C[0]-1][C[1]-1] = 0
visited[C[0]-1][C[1]-1] = True
dh = [0, 1, 0, -1]
dw = [1, 0, -1, 0]
warp = [[-1] * W for i in range(H)]
warp[C[0]-1][C[1]-1] = 0
warp_time = 0
warp_stock = deque([[C[0]-1, C[1]-1]])

while q or warp_stock:
    while q:
        ch, cw = q.popleft()
        warp_stock.append([ch, cw])
        dh = [0, 1, 0, -1]
        dw = [1, 0, -1, 0]
        for i in range(4):
            nh = ch + dh[i]
            nw = cw + dw[i]
            if 0 <= nh < H and 0 <= nw < W:
                if visited[nh][nw] == False and S[nh][nw] != "
                    
                    visited[nh][nw] = True
                    warp[nh][nw] = warp_time
                    
                    q.append([nh, nw])
        
    while warp_stock:
        ch, cw = warp_stock.popleft()
        for dh in [-2, -1, 0, 1, 2]:
            for dw in [-2, -1, 0, 1, 2]:
                nh = ch + dh
                nw = cw + dw
                if 0 <= nh < H and 0 <= nw < W:
                    if visited[nh][nw] == False and S[nh][nw] != "
                        
                        visited[nh][nw] = True
                        q.append([nh, nw])
                        warp[nh][nw] = warp_time + 1
    warp_time += 1
print(warp[D[0]-1][D[1]-1])

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque, defaultdict

    h, w = map(int, readline().split())
    sr, sc = map(int, readline().split())
    gr, gc = map(int, readline().split())

    grid = [["
    for _ in range(h):
        s = ["
        grid.append(s)
    grid.append(["

    ans = 0
    que1 = deque()
    que2 = deque()
    que1.append((sr, sc))
    grid[sr][sc] = "!"

    while que1 or que2:
        while que1:
            cr, cc = que1.popleft()
            que2.append((cr, cc))

            if cr == gr and cc == gc:
                return print(ans)

            if grid[cr + 1][cc] == ".":
                que1.appendleft((cr + 1, cc))
                grid[cr + 1][cc] = "!"
            if grid[cr - 1][cc] == ".":
                que1.appendleft((cr - 1, cc))
                grid[cr - 1][cc] = "!"
            if grid[cr][cc + 1] == ".":
                que1.appendleft((cr, cc + 1))
                grid[cr][cc + 1] = "!"
            if grid[cr][cc - 1] == ".":
                que1.appendleft((cr, cc - 1))
                grid[cr][cc - 1] = "!"

        ans += 1

        while que2:
            cr, cc = que2.popleft()
            for mr in range(-2, 3):
                for mc in range(-2, 3):
                    nr = cr + mr
                    nc = cc + mc
                    if 1 <= nr <= h and 1 <= nc <= w:
                        if grid[nr][nc] == ".":
                            que1.append((nr, nc))
                            grid[nr][nc] = "!"

    return print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys
input=sys.stdin.readline
H,W = map(int,input().split())
C_pos=list(map(lambda x:int(x)-1,input().split()))
D_pos=list(map(lambda x:int(x)-1,input().split()))
Grid=[[c for c in input()] for _ in range(H)]
Dist=[[float("inf")]*W for _ in range(H)]

DX=[0,0,1,-1]
DY=[1,-1,0,0]

Q=deque()
Q.append((C_pos[0],C_pos[1]))
DX=[-1,1,0,0]
visited=set()
prev_visited=set()

dist=0
while True:
    prev_visited=set(v for v in Q)
    if len(Q)==0:
        print(-1)
        exit()

    
    while Q:
        cx,cy=Q.pop()
        if cx==D_pos[0] and cy==D_pos[1]:
            print(dist)
            exit()

        visited.add((cx,cy))
        for dx,dy in zip(DX,reversed(DX)):
            nx = cx+dx
            ny=cy+dy
            if 0<=nx<H and 0<=ny<W and Grid[nx][ny]=="." and (nx,ny) not in visited:
                visited.add((nx,ny))
                prev_visited.add((nx,ny))
                Dist[nx][ny]=dist
                Q.append((nx,ny))
                if nx==D_pos[0] and ny==D_pos[1]:
                    print(dist)
                    exit()

    Q=deque()
    for cx,cy in prev_visited:
        for dx in range(-2,3):
            for dy in range(-2,3):
                if dx==0 and dy==0:
                    continue
                nx = cx+dx
                ny=cy+dy
                if (nx,ny) in visited:
                    continue
                if 0<=nx<H and 0<=ny<W and Grid[nx][ny]==".":
                    Q.append((nx,ny))
    dist+=1

Solution (Python):
import sys
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [list(map(str, list(input()))) for i in range(H)]
floor = [[0] * W for i in range(H)]
floor[Ch - 1][Cw - 1] = 1



def water(x, y):
    if floor[y][x] != 0:
        kouho.append([x, y])
        
        if y + 1 < H:
            if S[y + 1][x] != "
                floor[y + 1][x] = floor[y][x]
                water(x, y + 1)
        
        if y - 1 >= 0:
            if S[y - 1][x] != "
                floor[y - 1][x] = floor[y][x]
                water(x, y - 1)
        
        if x + 1 < W:
            if S[y][x + 1] != "
                floor[y][x + 1] = floor[y][x]
                water(x + 1, y)
        
        if x - 1 >= 0:
            if S[y][x - 1] != "
                floor[y][x - 1] = floor[y][x]
                water(x - 1, y)


def warp(x, y, i):
    for Y in range(max(y - 2, 0), min(y + 2, H - 1) + 1):
        for X in range(max(x - 2, 0), min(x + 2, W - 1) + 1):
            if S[Y][X] != "
                floor[Y][X] = i + 1
                water(X, Y)

kouho = deque()

water(Cw - 1, Ch - 1)



for i in range(1, 1000000):
    flag = False
    new_kouho = kouho.copy()
    kouho.clear()
    for n in new_kouho:
        x = n[0]
        y = n[1]
        if floor[y][x] == i:
            warp(x, y, i)
            flag = True

    if floor[Dh - 1][Dw - 1] != 0:
        print(floor[Dh - 1][Dw - 1] - 1)
        
        sys.exit()

    if flag == False:
        print("-1")
        sys.exit()

Solution (Python):
from collections import deque
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(10**7)

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


def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def neighbors4(x, y):
  dxy = (0, 1, 0, -1, 0 )
  for i in range(4):
    yield(x + dxy[i], y + dxy[i+1])

def search(cost, sx, sy):
    

    que = deque()
    que.append((sx,sy))

    reached = []

    while que:
        x,y = que.popleft()

        
        reached.append((x,y))

        if cost_map[y][x] <= cost:
            continue
        cost_map[y][x] = cost

        for x2, y2 in neighbors4(x,y):
            if x2<0 or x2>=w or y2<0 or y2>=h:
                continue
            if grid_s[y2][x2] == ".":
                que.append((x2, y2))
    
    return reached

def jump(cost, x, y):
    if cost >= cost_map[y][x]:
        return
    reached = search(cost, x, y)
    
    
    if cost_map[dh][dw] != INF:
        print(cost_map[dh][dw])
        exit()
    
    
    for x,y in reached:
        for y2 in range(max(0, y-2), min(h, y+3)):
            for x2 in range(max(0, x-2), min(w, x+3)):
                if abs(x-x2) + abs(y-y2) < 2:
                    continue
                if grid_s[y2][x2] == "." and cost_map[y2][x2] > cost+1:
                    heappush(jump_que, (cost+1, x2, y2))

def main():
    global h,w,dh,dw,grid_s,cost_map, jump_que,INF
    INF = 999999999999999999999999
    MOD = 10**9+7

    h,w = get_nums_l()
    ch,cw = get_nums_l()
    dh,dw = get_nums_l()

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

    grid_s = []
    for i in range(h):
        grid_s.append(input())
    
    cost_map = [[INF] * w for _ in range(h) ]

    jump_que = deque()
    jump_que.append((0, cw, ch))

    while jump_que:
        cost, x, y = jump_que.popleft()
        
        if cost >= cost_map[y][x]:
            continue
        reached = search(cost, x, y)
        
        
        if cost_map[dh][dw] != INF:
            print(cost_map[dh][dw])
            exit()
        
        
        for x,y in reached:
            for y2 in range(max(0, y-2), min(h, y+3)):
                for x2 in range(max(0, x-2), min(w, x+3)):
                    if abs(x-x2) + abs(y-y2) < 2:
                        continue
                    if grid_s[y2][x2] == "." and cost_map[y2][x2] > cost+1:
                        jump_que.append((cost+1, x2, y2))
    
    print(-1)

main()

Solution (Python):
from collections import deque
import time


def f1(x,y,xa,ya):
    if reach[xa][ya] == -1 or reach[xa][ya] > reach[x][y]:
         if c[xa][ya] == ".":
            reach[xa][ya] = reach[x][y]
            r.append([xa,ya])
            q.append([xa,ya])

            
            
def f2(x,y,xa,ya):
    if 0 <= xa <= h and 0 <= ya <= w:
    
        if reach[xa][ya] == -1 or reach[xa][ya] > reach[x][y] + 1:
            if c[xa][ya] == ".":
                reach[xa][ya] = reach[x][y] + 1
                q.append([xa,ya])

h,w = map(int,input().split())
cx, cy = map(int,input().split())
dx, dy = map(int,input().split())

t0 = time.time()

c = ["
for i in range(1,h+1):
    c[i] = ["
c[0]  = [0]*(w+2)
c[-1] = [0]*(w+2)

reach = [[-1 for j in range(w+2)] for i in range(h+2)]
q = deque([])

reach[cx][cy] = 0
q.append([cx,cy])

ans = 0

while q:
    
    if time.time() - t0 >= 1.5:
        break
    
    
    x,y = q.popleft()
    
    r = deque()
    r.append([x,y])
    while r:
        xx,yy = r.popleft()
        
        f1(xx,yy,xx-1,yy)
        f1(xx,yy,xx+1,yy)
        f1(xx,yy,xx,yy-1)
        f1(xx,yy,xx,yy+1)
    
    for i in range(-2,3):
        for j in range(-2,3):
            f2(x,y,x+i,y+j)


print(reach[dx][dy])

Solution (Python):
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(lambda s: int(s) - 1, input().split())
Dh, Dw = map(lambda s: int(s) - 1, input().split())
S = [input() for i in range(H)]

N = [[1000000007] * W for i in range(H)]
visited = [[False] * W for i in range(H)]
q = deque([(Ch, Cw)])
N[Ch][Cw] = 0
while len(q) > 0:
    Ph, Pw = q.popleft()
    if visited[Ph][Pw]:
        continue
    visited[Ph][Pw] = True
    for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nh = Ph + dh
        nw = Pw + dw
        if not 0 <= nh < H or not 0 <= nw < W or S[nh][nw] == '
            continue
        N[nh][nw] = min(N[nh][nw], N[Ph][Pw])
        if not visited[nh][nw]:
            q.appendleft((nh, nw))
    for dh in range(-2, 3):
        nh = Ph + dh
        if not 0 <= nh < H:
            continue
        for dw in range(-2, 3):
            nw = Pw + dw
            if not 0 <= nw < W or S[nh][nw] == '
                continue
            N[nh][nw] = min(N[nh][nw], N[Ph][Pw] + 1)
            if not visited[nh][nw]:
                q.append((nh, nw))

print(N[Dh][Dw] if visited[Dh][Dw] else -1)

Solution (Python):
def abc176_d():
    h, w = map(int, input().split())
    ch, cw = map(lambda x: int(x)-1, input().split())
    dh, dw = map(lambda x: int(x)-1, input().split())
    grid = [[x for x in str(input())] for _ in range(h)]
    
    area = [[-1]*w for _ in range(h)]
    aid = -1
    graph = []

    def dfs(i, j):
        nonlocal aid
        if area[i][j] > -1: return
        if grid[i][j] == '
        area[i][j] = aid
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if 0 <= i+dx and i+dx < h and 0 <= j+dy and j+dy < w:
                    v = area[i+dx][j+dy]
                    if v > -1 and v != aid:
                        graph[aid].add(v)
                        graph[v].add(aid)
        for dx, dy in [(-1,0),(0,-1),(0,1),(1,0)]:
            if 0 <= i+dx and i+dx < h and 0 <= j+dy and j+dy < w:
                dfs(i+dx, j+dy)

    for i in range(h):
        for j in range(w):
            if grid[i][j] == '.' and area[i][j] == -1:
                aid += 1
                graph.append(set())
                dfs(i, j)

    
    

    from collections import deque
    s = area[ch][cw]
    que = deque([s])
    dist = [-1] * (aid+1)
    dist[s] = 0
    while que:
        u = que.popleft()
        for i in graph[u]:
            if dist[i] == -1:
                dist[i] = dist[u] + 1
                que.append(i)
    
    ans = dist[area[dh][dw]]
    print(ans)

if __name__ == '__main__':
    abc176_d()

Solution (Python):
import sys
import heapq
INF=10**9
def Dijkstra(graph, start):
  dist={}
  for i in graph:
    dist[i]=INF
  queue=[(0, start)]
  while queue:
    path_len, v=heapq.heappop(queue)
    if dist[v]==INF: 
      dist[v]=path_len
      for w in graph[v]:
        if dist[w]==INF:
          heapq.heappush(queue, (dist[v]+1, w))         
  return dist
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())

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
m=[]
for i in range(h):
  s=input()
  m.append(s)
uf=UnionFind(h*w)
for i in range(h):
  for j in range(w):
    if j+1<w and m[i][j]=='.' and m[i][j+1]=='.':
      uf.union(i+h*j,i+h*(j+1))
    if i+1<h and m[i][j]=='.' and m[i+1][j]=='.':
      uf.union(i+h*j,i+1+h*j)
if uf.same((ch-1)+(cw-1)*h,(dh-1)+(dw-1)*h):
  print(0)
  sys.exit()
graph={}
for i in uf.roots():
  graph[i]=set()
for i in range(h):
  for j in range(w):
    if m[i][j]!='.':
      continue
    for k in range(-2,3):
      for l in range(3):
        if i+k<0 or i+k>=h or j+l>=w:
          continue
        if m[i+k][j+l]!='.' or uf.same(i+k+(j+l)*h,i+j*h):
          continue
        graph[uf.find(i+k+(j+l)*h)].add(uf.find(i+j*h))
        graph[uf.find(i+j*h)].add(uf.find(i+k+(j+l)*h))
dist=Dijkstra(graph,uf.find(ch-1+(cw-1)*h))
if dist[uf.find(dh-1+(dw-1)*h)]==INF:
  print(-1)
else:
  print(dist[uf.find(dh-1+(dw-1)*h)])