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

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
s = [input() for _ in range(h)]
inf = 99999999
dist = [[inf]* w for i in range(h)]
queue = []
queue.append([ch-1,cw-1])
dist[ch-1][cw-1] = 0

dx=[1,0,-1,0]
dy=[0,1,0,-1]

wx=[-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
wy=[-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
import sys
warp = 0
wall = []
while True:
    while queue!=[]:
        y,x = map(int, queue.pop())

        if x == dw-1 and y ==dh-1:
            print(dist[y][x])
            sys.exit()

        for i in range(len(dx)):
            next_x = x +dx[i]
            next_y = y +dy[i]

            if 0 <= next_x < len(s[0]) and 0 <= next_y < len(s):
                if dist[next_y][next_x] == inf: 
                    if s[next_y][next_x] == ".":
                        queue.append([next_y,next_x])
                        dist[next_y][next_x] = dist[y][x]
                    else:
                        wall.append([y,x]) 
    wall = list(map(list, set(map(tuple, wall))))
    while wall != []:
        y,x = map(int, wall.pop())
        for i in range(len(wx)):
            next_x = x +wx[i]
            next_y = y +wy[i]

            if 0 <= next_x < len(s[0]) and 0 <= next_y < len(s):
                if dist[next_y][next_x] == inf: 
                    if s[next_y][next_x] == ".":
                        queue.append([next_y,next_x])
                        dist[next_y][next_x] = dist[y][x]+1
    queue = list(map(list, set(map(tuple, queue))))
    
    if queue == []:
        print("-1")
        sys.exit()

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((b1[:, :], i8, i8, i8, i8), cache=True)
def main(wall, Sx, Sy, Tx, Ty):
    INF = 1 << 30
    H, W = wall.shape
    S = Sx * W + Sy
    T = Tx * W + Ty
    dist = np.full(H * W, INF, np.int64)
    deq = np.empty(H * W + 100, np.int64)
    dist[S] = 0
    deq[0], l, r = S, 0, 1
    while l < r:
        v, l = deq[l], l + 1
        vx, vy = divmod(v, W)
        
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            wx, wy = vx + dx, vy + dy
            if not (0 <= wx < H):
                continue
            if not (0 <= wy < W):
                continue
            if wall[wx, wy]:
                continue
            w = wx * W + wy
            if dist[w] <= dist[v]:
                continue
            dist[w] = dist[v]
            deq[l - 1], l = w, l - 1
        
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                wx, wy = vx + dx, vy + dy
                if not (0 <= wx < H):
                    continue
                if not (0 <= wy < W):
                    continue
                if wall[wx, wy]:
                    continue
                w = wx * W + wy
                if dist[w] <= dist[v] + 1:
                    continue
                dist[w] = dist[v] + 1
                deq[r], r = w, r + 1
    ans = dist[T]
    if ans == INF:
        ans = -1
    return ans

H, W = map(int, readline().split())
Sx, Sy = map(lambda x: int(x) - 1, readline().split())
Tx, Ty = map(lambda x: int(x) - 1, readline().split())
wall = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W] == b'

print(main(wall, Sx, Sy, Tx, Ty))

Solution (Python):
from itertools import combinations
import sys
from collections import defaultdict, deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
DDX = (-1, 0, 1, 0, -1, -1, 1, 1)
DDY = (0, 1, 0, -1, -1, 1, -1, 1)
DX = DDX[:4]
DY = DDY[:4]


H, W = map(int, input().split())
Cx, Cy = map(int, input().split())
Dx, Dy = map(int, input().split())

grid = ["
for _ in range(H):
    inp = "
    grid.append(inp)
grid.append("


area = [[-1] * (W + 2) for _ in range(H + 2)]
cnt = 0
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if grid[i][j] == "
            continue
        cnt += 1
        node = [(i, j)]
        area[i][j] = cnt
        while node:
            x, y = node.pop()
            for dx, dy in zip(DX, DY):
                nx = x + dx
                ny = y + dy
                if grid[nx][ny] == "
                    continue
                if area[nx][ny] == -1:
                    area[nx][ny] = cnt
                    node.append((nx, ny))


used = defaultdict(int)

edge = [[] for _ in range(cnt + 1)]
for i in range(1, H + 1):
    for j in range(1, W + 1):
        memo = set()
        if grid[i][j] == ".":
            memo.add(area[i][j])
        for dx, dy in zip(DDX, DDY):
            if area[i + dx][j + dy] == -1:
                continue
            memo.add(area[i + dx][j + dy])
        for x, y in combinations(memo, 2):
            if x > y:
                x, y = y, x
            if used[(x, y)]:
                continue
            edge[x].append(y)
            edge[y].append(x)
            used[(x, y)] = 1


dist = [-1] * (cnt + 1)
ci = area[Cx][Cy]
di = area[Dx][Dy]
dist[ci] = 0
node = deque([ci])
while node:
    s = node.popleft()
    for t in edge[s]:
        if dist[t] != -1:
            continue
        dist[t] = dist[s] + 1
        node.append(t)

print(dist[di])

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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(map(lambda x: x==".", input())) for i in range(h)]

inf = 2**32-1
count = [[inf]*w for i in range(h)]

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

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

while que:
    x,y,c = que.popleft()
    if count[x][y] <= c:
        continue
    count[x][y] = c
    kabe = False
    for dx,dy in dxdy:
        nx, ny = x+dx, y+dy
        if not (0<=nx<h and 0<=ny<w):
            continue
        if s[nx][ny]:
            que.appendleft((nx,ny,c))
        else:
            kabe = True
    if not kabe:
        continue
    nc = c+1
    for kx in range(-2,3):
        for ky in range(-2,3):
            nx = x+kx
            ny = y+ky
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > nc:
                que.append((nx,ny,nc))

ans = count[dh][dw]
if ans == inf:
    ans = -1
print(ans)

Solution (Python):
import collections
import itertools

h, w = map(int, input().split())
sy, sx = map(lambda x:int(x) - 1, input().split())
gy, gx = map(lambda x:int(x) - 1, input().split())
maze = [list(input()) for _ in range(h)]

seen = [[-1] * w for _ in range(h)]
seen[sy][sx] = 0
que = collections.deque()
que.append((sy, sx))
tmp2 = [(sy, sx)]
cnt = 0
while True:
    tmp1 = []
    for sy, sx in tmp2:
        if maze[sy][sx] == ".":
            que.append((sy,sx))
            tmp1.append((sy, sx))
            while que:
                py, px = que.popleft()
                for dy, dx in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                    ny = py + dy
                    nx = px + dx
                    if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] == "." and seen[ny][nx] == -1:
                        seen[ny][nx] = cnt
                        que.append((ny, nx))
                        tmp1.append((ny, nx))
                        maze[sy][sx] = "
                        
    if seen[gy][gx] != -1:
        break

    flag = True
    d = [-2, -1, 0, 1, 2]
    tmp2 = []
    for py, px in tmp1:
        for i in range(5):
            for j in range(5):
                ny = py + d[i]
                nx = px + d[j]
                if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] == "." and seen[ny][nx] == -1:
                    seen[ny][nx] = cnt + 1
                    que.append((ny, nx))
                    flag = False
                    tmp2.append((ny, nx))
    cnt += 1
    if flag:
        break
    if seen[gy][gx] != -1:
        break

print(seen[gy][gx])

Solution (Python):
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(map(lambda x: x==".", input())) for i in range(h)]

inf = 2**32-1
count = [[inf]*w for i in range(h)]

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

dxdy = [(-1,0),(0,1),(1,0),(0,-1)]
dxdy1 = [(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
dxdy2 = [(-1,1),(-1,2),(-2,1),(-2,2)]
dxdy3 = [(1,1),(1,2),(2,1),(2,2)]
dxdy4 = [(1,-1),(1,-2),(2,-1),(2,-2)]
while que:
    x,y,c = que.popleft()
    if count[x][y] <= c:
        continue
    count[x][y] = c
    state = [False]*4
    for i, (dx,dy) in enumerate(dxdy):
        nx, ny = x+dx, y+dy
        if not (0<=nx<h and 0<=ny<w):
            continue
        if s[nx][ny]:
            que.appendleft((nx,ny,c))
        else:
            state[i] = True
            nx,ny = nx+dx, ny+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))

    if state[-1] and state[0]:
        for dx,dy in dxdy1:
            nx, ny = x+dx, y+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))

    if state[0] and state[1]:
        for dx,dy in dxdy2:
            nx, ny = x+dx, y+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))
    if state[1] and state[2]:
        for dx,dy in dxdy3:
            nx, ny = x+dx, y+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))
    if state[2] and state[3]:
        for dx,dy in dxdy4:
            nx, ny = x+dx, y+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))

ans = count[dh][dw]
if ans == inf:
    ans = -1
print(ans)

Solution (Python):

import sys,math,collections,itertools
input = sys.stdin.readline
 
H,W=list(map(int,input().split()))
Ch,Cw=list(map(int,input().split()))
Dh,Dw=list(map(int,input().split()))
s=[ input().rstrip() for _ in range(H)]
 

dp = [ [float('inf') ]*W  for _ in range(H)]
 
q = collections.deque([])
q.append((Ch-1,Cw-1))
dp[Ch-1][Cw-1]=0
while q:
    visit = []
    while q:
        nh,nw = q.popleft()
        visit.append((nh,nw))
        
        if nh>0 and s[nh-1][nw] =='.' and dp[nh-1][nw]>dp[nh][nw]:
            q.append((nh-1,nw))
            dp[nh-1][nw] = dp[nh][nw]
        if nh<H-1 and s[nh+1][nw] =='.' and dp[nh+1][nw]>dp[nh][nw]:
            q.append((nh+1,nw))
            dp[nh+1][nw] = dp[nh][nw]
        if nw>0 and s[nh][nw-1] =='.' and dp[nh][nw-1]>dp[nh][nw]:
            q.append((nh,nw-1))
            dp[nh][nw-1] = dp[nh][nw]
        if nw<W-1 and s[nh][nw+1] =='.' and dp[nh][nw+1]>dp[nh][nw]:
            q.append((nh,nw+1))
            dp[nh][nw+1] = dp[nh][nw]
    while visit:
    
        nh,nw = visit.pop()
        for ih in range(-2,3,1):
            for iw in range(-2,3,1):
                if (0<= nh+ih<=H-1) and (0<=nw+iw<=W-1):
                    if s[nh+ih][nw+iw] =='.' and dp[nh+ih][nw+iw]>dp[nh][nw]:
                        q.append((nh+ih,nw+iw))
                        dp[nh+ih][nw+iw] = dp[nh][nw]+1
     
 
ans = dp[Dh-1][Dw-1]
print(-1 if ans==float('inf') else ans)

Solution (Python):
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools
from math import *
from bisect import *
from heapq import *
from collections import *
import queue

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

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()



H, W = In.ints()

grid = [["." for j in range(W)] for i in range(H)]

C = In.ints()
C = (C[0]-1, C[1]-1)
D = In.ints()
D = (D[0]-1, D[1]-1)

for i in range(H):
    s = In.str()

    for j in range(W):
        grid[i][j] = s[j]    



moves = [[0,1], [0,-1], [1,0], [-1,0]]
setnext = set()
setnow = set([(C[0], C[1])])
quenow = deque([(C[0], C[1])])

ans = 0
found = False
hadOne = True

while hadOne:
    hadOne=False
    while len(quenow)>0:
        hadOne=True
        now = quenow.popleft()

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

                if 0<=nex[0]<H and 0<=nex[1]<W and grid[nex[0]][nex[1]]==".":
                    if nex not in setnow and nex not in setnext:
                        setnext.add(nex)                    

        for m in moves:
            nex = (now[0]+m[0], now[1]+m[1])

            if nex == D:
                found = True
                break

            if 0<=nex[0]<H and 0<=nex[1]<W and grid[nex[0]][nex[1]] == "." and nex not in setnow:
                quenow.append(nex)
                setnow.add(nex)
        
        if found:
            break
    
    if found:
        break
    
    ans += 1

    for el in setnext:
        if el==D:
            found=True
            break
        if el not in setnow:            
            setnow.add(el)
            quenow.append(el)
    
    setnext.clear()
    
    if found:
        break


if found:
    Out.int(ans)
else:
    Out.int(-1)


if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

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):
    
    HEIGHT = H + 4
    WIDTH = W + 4
    N = HEIGHT * WIDTH
    visited = [0] * N
    distance = [0] * N
    jump = [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
            distance[p] = currentDistance
            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 main():
    
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    D = [0] * ((H + 4) * (W + 4))
    for i in range(H):
        S = input().strip()
        for j in range(W):
            D[(i + 2) * (W + 4) + (j + 2)] = 1 if S[j] == ord(b".") else 0
    
    
    
    
    
    
    
    
    
    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
from itertools import product

H, W =map(int,input().split())
C=tuple(map(lambda x: int(x)-1,input().split()))
D=tuple(map(lambda x: int(x)-1,input().split()))
S=[input().strip("¥n") for i in range(H)]

mag=(-2, -1, 0, 1, 2)

dist=[[-1]*W for i in range(H)]

qu=deque([(C[0], C[1])])
dist[C[0]][C[1]]=0

while(len(qu)>0):
  qut=deque()
  while(len(qu)>0):
    v=qu.popleft()
    qut.append(v)
    for h,w in ((-1,0),(1,0),(0,-1),(0,1)):
      nvh=v[0]+h
      nvw=v[1]+w
      if 0<=nvh<H and 0<=nvw<W and dist[nvh][nvw]==-1 and S[nvh][nvw]==".":
        dist[nvh][nvw]=dist[v[0]][v[1]]
        qu.append((nvh,nvw))
  while(len(qut)>0):
    v=qut.popleft()
    for h,w in product(mag,repeat=2):
      if h==0 and w==0:
        continue
      nvh=v[0]+h
      nvw=v[1]+w
      if 0<=nvh<H and 0<=nvw<W and S[nvh][nvw]==".":
        if dist[nvh][nvw]==-1:
          dist[nvh][nvw]=dist[v[0]][v[1]]+1
          qu.append((nvh,nvw))
print(dist[D[0]][D[1]])

Solution (Python):
import sys


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


def _ia(): return map(int, sys.stdin.readline().strip().split())


def walk(s, w1, h1, x, y, cur, v1, v2):
    if s[y][x] is not None:
        return
    s[y][x] = cur
    v1.add((x, y))
    for hi in range(max(0, y - 2), min(h1, y + 2) + 1):
        for wi in range(max(0, x - 2), min(w1, x + 2) + 1):
            if s[hi][wi] is None:
                v2.add((wi, hi))

    if x > 0:
        walk(s, w1, h1, x-1, y, cur, v1, v2)
    if x < w1:
        walk(s, w1, h1, x+1, y, cur, v1, v2)
    if y > 0:
        walk(s, w1, h1, x, y-1, cur, v1, v2)
    if y < h1:
        walk(s, w1, h1, x, y+1, cur, v1, v2)


def main():
    h, w = _ia()
    sh, sw = map(lambda x: x-1, _ia())
    gh, gw = map(lambda x: x-1, _ia())
    s = [[0]*w for _ in range(h)]
    for hi in range(h):
        for wi, c in enumerate(_s()):
            if c == '.':
                s[hi][wi] = None
            else:
                s[hi][wi] = -1

    p = [(sw, sh)]
    c = 0
    h1, w1 = h-1, w-1
    while len(p) > 0:
        v1 = set()
        v2 = set()
        for pi in p:
            walk(s, w1, h1, *pi, c, v1, v2)
        p = v2 - v1
        c += 1
    ans = s[gh][gw]
    return ans if ans is not None else -1


if __name__ == "__main__":
    print(main())

Solution (Python):
h, w = [int(i) for i in input().split()]
ch, cw = [int(i) for i in input().split()]
ch -= 1
cw -= 1
dh, dw = [int(i) for i in input().split()]
dh -= 1
dw -= 1

loc = []
move = []
checked = []
magicchecked = []
for i in range(h):
    line = input()
    loc.append([j for j in line])
    move.append([-1 for j in line])
    checked.append([0 for j in line])
    magicchecked.append([0 for j in line])

move[ch][cw] = 0
cur = 0
walk = [(ch, cw)]
walkhistory = []
magic = []
while len(walk) > 0:
    node = walk.pop()
    walkhistory.append(node)
    checked[node[0]][node[1]] = 1
    if node[0] - 1 >= 0 and loc[node[0] - 1][node[1]] != "
        walk.append((node[0] - 1, node[1]))
    if node[1] - 1 >= 0 and loc[node[0]][node[1] - 1] != "
        walk.append((node[0], node[1] - 1))
    if node[0] + 1 < h and loc[node[0] + 1][node[1]] != "
        walk.append((node[0] + 1, node[1]))
    if node[1] + 1 < w and loc[node[0]][node[1] + 1] != "
        walk.append((node[0], node[1] + 1))
    move[node[0]][node[1]] = cur
    i = node[0]
    j = node[1]

for node in walkhistory:
    i = node[0]
    j = node[1]
    for k in range(-2, 3):
        for l in range(-2, 3):
            if i + k >= 0 and i + k < h and j + l >= 0 and j + l < w \
            and loc[i + k][j + l] == "." and checked[i + k][j + l] == 0 and magicchecked[i + k][j + l] == 0:
                magicchecked[i + k][j + l] = 1
                magic.append((i + k, j + l))

cur += 1

while magic:
    walk = magic[:]
    magic = []
    walkhistory = []

    while len(walk) > 0:
        node = walk.pop()
        walkhistory.append(node)
        checked[node[0]][node[1]] = 1
        if node[0] - 1 >= 0 and loc[node[0] - 1][node[1]] != "
            walk.append((node[0] - 1, node[1]))
        if node[1] - 1 >= 0 and loc[node[0]][node[1] - 1] != "
            walk.append((node[0], node[1] - 1))
        if node[0] + 1 < h and loc[node[0] + 1][node[1]] != "
            walk.append((node[0] + 1, node[1]))
        if node[1] + 1 < w and loc[node[0]][node[1] + 1] != "
            walk.append((node[0], node[1] + 1))
        move[node[0]][node[1]] = cur
        i = node[0]
        j = node[1]

    for node in walkhistory:
        i = node[0]
        j = node[1]
        for k in range(-2, 3):
            for l in range(-2, 3):
                if i + k >= 0 and i + k < h and j + l >= 0 and j + l < w \
                and loc[i + k][j + l] == "." and checked[i + k][j + l] == 0 and magicchecked[i + k][j + l] == 0:
                    magicchecked[i + k][j + l] = 1
                    magic.append((i + k, j + l))


    cur += 1

print(move[dh][dw])

Solution (Python):
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop
 

 
n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]
 
def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)
 
H, W = nn()
Ch, Cw = nn()
Dh, Dw = nn()
S = sm(H)
 
T = [u"
for s in S:
    T.append("
T += [u"
 
H += 4
W += 4
Ch += 2 - 1
Cw += 2 - 1
Dh += 2 - 1
Dw += 2 - 1
 
deq1 = deque()
deq1.append((Ch, Cw))
deq2 = deque()
 
cnt = 0
 
memo = array2(H, W, 10**6)
memo[Ch][Cw] = 0
 
memo2 = deque()

for i in range(10**6):
    
    
    
 
    if len(deq1) == 0:
        print(-1)
        exit(0)
 
    while len(deq1) > 0:
        h, w = deq1.pop()
        memo2.append((h, w))

        if h == Dh and w == Dw:
            print(i)
            exit(0)
 
        def sch(x, y, i):
            
            if T[x][y] == "." and i < memo[x][y]:
                memo[x][y] = i
                deq1.append((x, y))
 
        sch(h+1, w, i)
        sch(h-1, w, i)
        sch(h, w+1, i)
        sch(h, w-1, i)
 
    
    
    while len(memo2) > 0:
        j, k = memo2.pop()
        if memo[j][k] == i:
            for l in range(-2, 3):
                for m in range(-2, 3):
                    if T[j+l][k+m] == "." and i + 1 < memo[j+l][k+m]:
                        memo[j+l][k+m] = i + 1
                        deq2.append((j+l, k+m))
 
    deq1 = deq2
    deq2 = deque()
    memo2 = deque()

Solution (Python):
INF = 10**10
H, W = [int(i) for i in input().split(" ")]
Ch, Cw = [int(i) + 1 for i in input().split(" ")]
Dh, Dw = [int(i) + 1 for i in input().split(" ")]
S = [[False for i in range(W + 4)], [False for i in range(W + 4)]]
for i in range(H):
    S.append([False, False] + [j == '.' for j in input()] + [False, False])
S += [[False for i in range(W + 4)], [False for i in range(W + 4)]]


def check(h, w, island_num):
    assert S[h][w]
    block[h][w] = island_num
    if S[h - 1][w] and block[h - 1][w] == -1:
        check(h - 1, w, island_num)
    if S[h + 1][w] and block[h + 1][w] == -1:
        check(h + 1, w, island_num)
    if S[h][w - 1] and block[h][w - 1] == -1:
        check(h, w - 1, island_num)
    if S[h][w + 1] and block[h][w + 1] == -1:
        check(h, w + 1, island_num)


block = []
for i in range(H + 4):
    block.append([-1 for j in range(W + 4)])

island_num = 0

for h in range(H + 4):
    for w in range(W + 4):
        if S[h][w] and block[h][w] == -1:
            check(h, w, island_num)
            island_num += 1


neighbor = {}
for island in range(island_num):
    neighbor[island] = set()


for h in range(2, H + 2):
    for w in range(2, W + 2):
        if block[h][w] != -1:
            for y in range(h - 2, h + 3):
                for x in range(w - 2, w + 3):
                    if block[y][x] != -1 and block[h][w] != block[y][x]:
                        neighbor[block[h][w]].add(block[y][x])


start = block[Ch][Cw]
goal = block[Dh][Dw]
assert start != -1
assert goal != -1


dist = [INF for i in range(island_num)]
dist[start] = 0

nexts = [start]
while True:
    _nexts = []
    for n in nexts:
        for neigh in neighbor[n]:
            assert neigh != -1
            if dist[neigh] > dist[n] + 1:
                _nexts.append(neigh)
                dist[neigh] = dist[n] + 1
    nexts = list(set(_nexts))
    if len(nexts) == 0:
        break

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

Solution (Python):
h,w=map(int, input().split())
ch,cw=map(int, input().split())
ch-=1
cw-=1
dh,dw=map(int, input().split())
dh-=1
dw-=1
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
for i in range(h):
    for j in range(w):
        if grid[i][j]==0:
            col+=1
            stack=deque([(i,j)])
            grid[i][j]=col
            while stack:
                nowi,nowj=stack.popleft()
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))
                        grid[nowi+di][nowj+dj]=col
start=grid[ch][cw]-1
end=grid[dh][dw]-1
if start==end:
    print(0)
    exit()
es=[set([]) for _ in range(col)]
visited=[-1]*col

for i in range(h):
    for j in range(w):
        now=grid[i][j]
        if now!=-1: 
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if 0<=i+x<h and 0<=j+y<w:
                        nex=grid[i+x][j+y]
                        if nex!=-1 and now!=nex:
                            es[now-1].add(nex-1)

stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=visited[now]+1
            stack.append(e)

print(visited[end])

Solution (Python):
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
h,w=map(int,input().split())
nx,ny=map(int,input().split())
gx,gy=map(int,input().split())
maze=[input()for i in range(h)]
from heapq import heapify, heappop, heappush
seen=set()
gx-=1;gy-=1
SIZE=h*w
hq=[(nx-1)*w+ny-1]
while hq:
    d=heappop(hq)
    c,d=divmod(d,SIZE)
    x,y=divmod(d,w)
    if w*x +y in seen:continue
    seen.add(w*x +y)
    if x==gx and y==gy:print(c);exit()
    if x and w*(x-1)+y not in seen and maze[x-1 ][y]!=35:
        heappush(hq,(c*SIZE+w*(x-1)+y))
    if y and w*x+y-1 not in seen and maze[x][y-1]!=35:
        heappush(hq,(c*SIZE+w*x+y-1))
    if x+1<h  and w*(x+1)+y not in seen and maze[x+1][y]!=35:
        heappush(hq,(c*SIZE+w*(x+1)+y))
    if y+1<w  and w*x+y+1 not in seen and maze[x][y+1]!=35:
        heappush(hq,(c*SIZE+w*x+y+1))
    for i in range(max(0,x-2),min(h,x+3)):
        for j in range(max(0,y-2),min(w,y+3)):
            if i==x and j==y:continue
            if maze[i][j]==46 and w*i + j not in seen:
                heappush(hq,(c+1)*SIZE+w*i+j)

print(-1)