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):
from collections import deque


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())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  


walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

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

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  
    for dx, dy in warp:  
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Solution (Python):



from collections import deque

H, W = map(int,input().split())
sth, stw = map(int,input().split())
glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
direc5 = set([])
for i in range(-2,3):
    for j in range(-2,3):
        direc5.add((i, j))
direc5 = direc5 - direc
direc5 = direc5 - {(0,0)}
nxt_st = set([])

def bfs(pnxt):
    next_q = deque([])
    for hw in pnxt:
        next_q.append(hw)
    nxt = set([])
    while len(next_q)!=0:
        
        h,w = next_q.popleft()
        if h == glh and w == glw:
            print(ret)
            exit()
        seen[h][w] = 0
        for dh, dw in direc:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF:
                next_q.append((hs, ws))
                seen[hs][ws] = 0
        for dh, dw in direc5:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF:
                nxt.add((hs, ws))

    return nxt

ret = -1
nxt_st.add((sth, stw))
while len(nxt_st)>0:
    ret += 1
    nxt_st = bfs(nxt_st)
print(-1)

Solution (Python):



from collections import deque

H, W = map(int,input().split())
sth, stw = map(int,input().split())
glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
direc5 = set([])
for i in range(-2,3):
    for j in range(-2,3):
        direc5.add((i, j))
direc5 = direc5 - direc
direc5 = direc5 - {(0,0)}

def bfs(pnxt):
    next_q = deque([])
    for h, w in pnxt:
        next_q.append((h,w))
        seen[h][w] = 0
    nxt = set([])
    while len(next_q)!=0:
        h, w = next_q.popleft()
        if h == glh and w == glw:
            print(ret)
            exit()
        for dh, dw in direc:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF:
                next_q.append((hs, ws))
                seen[hs][ws] = 0
        for dh, dw in direc5:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF and not (hs, ws) in nxt:
                nxt.add((hs, ws))
    return nxt

ret = 0
nxt_st = set([])
nxt_st.add((sth, stw))
while len(nxt_st)>0:
    nxt_st = bfs(nxt_st)
    ret += 1
print(-1)

Solution (Python):
from operator import itemgetter, attrgetter
import sys
readlines = sys.stdin.readlines
input = sys.stdin.readline
 
class RadixHeap:
    def __init__(self, C=1 << 31):
        self.last = 0
        self.size = 0
        self.v = [[] for _ in range(C.bit_length()+1)]
 
    def push(self, key, val):
        self.size += 1
        self.v[(key ^ self.last).bit_length()].append((key, val))
 
    def pop(self):
        v = self.v
        if not v[0]:
            i = 1
            while not v[i]:
                i += 1
            vi = v[i]
            new_last, _ = min(vi, key=itemgetter(0))
            for key, val in vi:
                v[(key ^ new_last).bit_length()].append((key, val))
            self.last = new_last
            vi.clear()
        self.size -= 1
        return v[0].pop()
 
    def __len__(self): return self.size

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 = readlines()
 
INF = 10**10
D = [[INF]*W for _ in [0]*H]
 
q = RadixHeap()
q.push(0, Ch*W+Cw)
 
while q:
    d, ij = q.pop()
    i, j = divmod(ij, W)
 
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            I = i+di
            J = j+dj
            if 0 <= I < H and 0 <= J < W and S[I][J] == '.':
                if abs(di)+abs(dj) == 1:
                    if D[I][J] <= d:
                        continue
                    D[I][J] = d
                    q.push(d, I*W+J)
                else:
                    if D[I][J] <= d+1:
                        continue
                    D[I][J] = d+1
                    q.push(d+1, I*W+J)
 
ans = D[Dh][Dw]
print(ans if ans < INF else -1)

Solution (Python):
from collections import deque
INF = 10**10
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
mat = []
for _ in range(h):
    s = input()
    mat.append(s)

costs = [[INF for _ in range(w)] for _ in range(h)]
costs[ch-1][cw-1] = 0
queue = deque()
queue.append((ch-1, cw-1))
while len(queue) > 0:
    x, y = queue.popleft()
    for i in range(4):
        dx = [-1, 0, 1, 0][i]
        dy = [0, -1, 0, 1][i]
        nx = x+dx
        ny = y+dy
        if nx < 0 or h <= nx or ny < 0 or w <= ny:
            continue
        if mat[nx][ny] == "
            continue
        if costs[nx][ny] > costs[x][y]:
            costs[nx][ny] = costs[x][y]
            queue.appendleft((nx, ny))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx = x+i
            ny = y+j
            if nx < 0 or h <= nx or ny < 0 or w <= ny:
                continue
            if mat[nx][ny] == "
                continue
            if costs[nx][ny] > costs[x][y] + 1:
                costs[nx][ny] = costs[x][y] + 1
                queue.append((nx, ny))
if costs[dh-1][dw-1] == INF:
    print(-1)
else:
    print(costs[dh-1][dw-1])

Solution (Python):
from collections import deque
H,W = map(int,input().split())
sy,sx = map(int,input().split())
sy-=1
sx-=1
gy,gx = map(int,input().split())
gy,gx = gy-1,gx-1
grid = [0] * H
done = [[0]*W for _ in range(H)]
cost = [[float('inf')]*W for _ in range(H)]
cost[sy][sx] = 0
done[sy][sx] =1
for i in range(H):
    grid[i] = input()

walk_q = deque()
magic_q = deque()
def walk_bfs(magic_count):
    y,x = walk_q.popleft()
    magic_q.append([y,x])
    for new_y,new_x in [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]:
        if 0<=new_y<H and 0<=new_x<W and grid[new_y][new_x] == '.':
            if not done[new_y][new_x]:
                done[new_y][new_x] = 1
                cost[new_y][new_x] = min(cost[new_y][new_x],magic_count)

                walk_q.append([new_y,new_x])
                magic_q.append([new_y,new_x])

def magic_bfs(magic_count):
    y,x = magic_q.popleft()
    for y_add in range(-2,3):
        for x_add in range(-2,3):
            if y_add == 0 and x_add == 0:
                continue
            new_y = y+y_add
            new_x = x+x_add

            if 0<=new_y<H and 0<=new_x<W and grid[new_y][new_x] == '.':
                if not done[new_y][new_x]:
                    done[new_y][new_x] = 1
                    cost[new_y][new_x] = min(cost[new_y][new_x],magic_count+1)

                    walk_q.append([new_y,new_x])

walk_q.append([sy,sx])
magic_q.append([sy,sx])
magic_count = 0


while walk_q or magic_q:
    while walk_q:
        walk_bfs(magic_count)
    while magic_q:
        magic_bfs(magic_count)
    magic_count += 1
if done[gy][gx]:
    print(cost[gy][gx])
else:
    print(-1)

Solution (Python):
import sys
from collections import deque

H, W = map(int, input().split())
Ch, Cw = (int(i) - 1 for i in input().split())
Dh, Dw = (int(i) - 1 for i in input().split())
G = [list(sys.stdin.readline().strip()) for _ in range(H)]

def bfs(start):
    zeroQ = deque()
    oneQ = deque()
    zeroQ.append(start)
    dist[start[1]][start[0]] = 0

    while zeroQ or oneQ:
        if zeroQ:
            x, y = zeroQ.popleft()
        else:
            x, y = oneQ.popleft()
        
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx = x + dx
                ny = y + dy
                
                if not(0 <= nx < W and 0 <= ny < H):
                    continue
                if G[ny][nx] == '
                    continue
                if abs(dx) + abs(dy) == 0:
                    continue
                
                cost = 0 if abs(dx) + abs(dy) == 1 else 1
                
                if dist[ny][nx] <= dist[y][x] + cost:
                    continue
                dist[ny][nx] = dist[y][x] + cost
                
                if cost == 0:
                    zeroQ.append((nx, ny))
                else:
                    oneQ.append((nx, ny))

dist = [[10 ** 9 for _ in range(W)] for _ in range(H)]

bfs((Cw, Ch))


if dist[Dh][Dw] == 10 ** 9:
    print(-1)
else:
    print(dist[Dh][Dw])

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**8)

def main():
    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 = [list(input()) for _ in range(H)]
    visited = [[False] * W for _ in range(H)]
    cnt = [[float('inf')] * W for _ in range(H)]
    dh = [1,0,-1,0]
    dw = [0,1,0,-1]
    visited[Ch][Cw] = True
    cnt[Ch][Cw] = 0
    Q = deque([[Ch,Cw]])
    while Q:
        h, w = Q.popleft()
        c = cnt[h][w]
        if h == Dh and w == Dw:
            break
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                if cnt[nh][nw] > c:
                    cnt[nh][nw] = c
                    Q.appendleft([nh,nw])
        nc = c + 1
        for j in range(-2,3):
            for k in range(-2,3):
                nh = h + j
                nw = w + k
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                    if cnt[nh][nw] > nc:
                        cnt[nh][nw] = nc
                        Q.append([nh,nw])

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




if __name__ == "__main__":
    main()

Solution (Python):
import sys
from heapq import *

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=list(sys.stdin)

ans=-1
hp=[(0,si,sj)]
dirs=[-2,-1,0,1,2]
dist=[[float('inf')]*W for _ in range(H)]
dist[si][sj]=0
while hp:
    k,i,j=heappop(hp)
    if i==ti and j==tj:
        ans=k
        break
    if k>dist[i][j]:
        continue
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='
                continue
            if abs(di)+abs(dj)==1:
                nk=k
            else:
                nk=k+1
            if nk>=dist[ni][nj]:
                continue
            dist[ni][nj]=nk
            heappush(hp,(nk,ni,nj))

print(ans)

Solution (Python):
import sys
from heapq import *

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=list(sys.stdin)

ans=-1
hp=[(0,si,sj)]
dirs=[-2,-1,0,1,2]
dist=[[float('inf')]*W for _ in range(H)]
dist[si][sj]=0
while hp:
    k,i,j=heappop(hp)
    if i==ti and j==tj:
        ans=k
        break
    if k>dist[i][j]:
        continue
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='
                continue
            if abs(di)+abs(dj)==1:
                nk=k
            else:
                nk=k+1
            if nk>=dist[ni][nj]:
                continue
            dist[ni][nj]=nk
            heappush(hp,(nk,ni,nj))

print(ans)

Solution (Python):
import queue
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
graphlist = []
replacelist = []
grapht = [[-1 for i in range(w+2)] for i in range(h+2)]
meiro = [["
lastnum=[0]
donelist = set()
for i in range(1, h+1):
    for j in range(1, w+1):
        if(meiro[i][j] == "."):
            if(grapht[i-1][j] != -1):
                grapht[i][j] = grapht[i-1][j]
            elif(grapht[i][j-1] != -1):
                grapht[i][j] = grapht[i][j-1]
            elif(grapht[i+1][j] != -1):
                grapht[i][j] = grapht[i+1][j]
            elif(grapht[i][j+1] != -1):
                grapht[i][j] = grapht[i][j+1]
            else:
                grapht[i][j] = lastnum
                graphlist.append(set())
                replacelist.append([])
                lastnum = [lastnum[0] + 1]
            if(meiro[i+1][j] == "."):
                grapht[i+1][j] = grapht[i][j]
            if(meiro[i][j+1] == "."):
                if(grapht[i][j+1] == -1):
                    grapht[i][j+1] = grapht[i][j]
                elif(grapht[i][j][0] != grapht[i][j+1][0]):
                        donelist.add(grapht[i][j+1][0])
                        graphlist[grapht[i][j][0]] = graphlist[grapht[i][j][0]] | (graphlist[grapht[i][j+1][0]] - set(grapht[i][j]))
                        for k in graphlist[grapht[i][j+1][0]]:
                            graphlist[k].add(grapht[i][j][0])
                        for k, l in replacelist[grapht[i][j+1][0]]:
                            grapht[k][l][0] = grapht[i][j][0]
                            replacelist[grapht[i][j][0]].append((k, l))
                        grapht[i][j+1][0] = grapht[i][j][0]
                        replacelist[grapht[i][j][0]].append((i,j+1))
                        replacelist[grapht[i][j][0]].append((i,j))
            for k in range(i-2, i+3):
                if(k >= h+1):
                    continue
                for l in range(j-2, j+3):
                    if(l >= w+1):
                        continue
                    if(grapht[k][l] != -1 and grapht[k][l] != grapht[i][j]):
                        graphlist[grapht[i][j][0]].add(grapht[k][l][0])
                        graphlist[grapht[k][l][0]].add(grapht[i][j][0])
start = grapht[ch][cw][0]
end = grapht[dh][dw][0]
nextlist = queue.Queue()
depthlist = [-1]*len(graphlist)
donelist.add(start)
depthlist[start] = 0
while True:
    for i in graphlist[start]:
        if(i not in donelist):
            nextlist.put(i)
            depthlist[i] = depthlist[start]+1
            donelist.add(i)
    if(nextlist.empty()):
        break
    start = nextlist.get()



print(depthlist[end])

Solution (Python):
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict 
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  
  
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright






h,w=map(int,input().split())
sx,sy=map(int,input().split()) ; sx-=1;sy-=1
gx,gy=map(int,input().split()) ;gx-=1;gy-=1

A=[]
for i in range(h):
    A.append(list(input()))

dp=[[10**6]*w for i in range(h)]
dp[sx][sy]=0
dx=[-1,0,1,0]
dy=[0,1,0,-1]

def warp(x,y):
    r=[]    
    for i in range(x-2,x+3):
        for j in range(y-2,y+3):
            if 0<=i<h and 0<=j<w:
                if not (i==x and j==y):
                    if A[i][j]==".":
                        r.append([i,j])
    return r

queue=deque([[sx,sy]])
while queue:
    x,y=queue.pop()
    for i,j in zip(dx,dy):
        if 0<=x+i<h and 0<=y+j<w and dp[x+i][y+j]>dp[x][y] and A[x+i][y+j]==".":
            dp[x+i][y+j]= dp[x][y]
            queue.append([x+i,y+j])
    for a,b in warp(x,y):
        if dp[a][b]>dp[x][y]+1:
            dp[a][b]= dp[x][y]+1
            queue.appendleft([a,b])

print(dp[gx][gy] if dp[gx][gy]!=10**6 else -1)

Solution (Python):
from collections import deque


def main():
    from sys import stdin
    readline = stdin.readline

    from builtins import max, min, range

    INF = 10 ** 6

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

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    warp_count = 0
    warpq = []
    while q:
        while q:
            warpq.append(q[0])
            h, w = q.popleft()
            if h - 1 >= 0 and t[h - 1][w] > warp_count:
                q.append((h - 1, w))
                t[h - 1][w] = warp_count
            if h + 1 < H and t[h + 1][w] > warp_count:
                q.append((h + 1, w))
                t[h + 1][w] = warp_count
            if w - 1 >= 0 and t[h][w - 1] > warp_count:
                q.append((h, w - 1))
                t[h][w - 1] = warp_count
            if w + 1 < W and t[h][w + 1] > warp_count:
                q.append((h, w + 1))
                t[h][w + 1] = warp_count

        if t[Dh][Dw] != INF:
            break

        warp_count += 1
        for h, w in warpq:
            for i in range(max(0, h - 2), min(H, h + 3)):
                ti = t[i]
                for j in range(max(0, w - 2), min(W, w + 3)):
                    if ti[j] > warp_count:
                        ti[j] = warp_count
                        q.append((i, j))
        warpq.clear()

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()

Solution (Python):
from collections import deque


def main():
    from sys import stdin
    readline = stdin.readline

    from builtins import max, min, range

    INF = 10 ** 6

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

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    a = 0
    warpq = []
    while q:
        while q:
            warpq.append(q[0])
            h, w = q.popleft()
            if h - 1 >= 0 and t[h - 1][w] > a:
                q.append((h - 1, w))
                t[h - 1][w] = a
            if h + 1 < H and t[h + 1][w] > a:
                q.append((h + 1, w))
                t[h + 1][w] = a
            if w - 1 >= 0 and t[h][w - 1] > a:
                q.append((h, w - 1))
                t[h][w - 1] = a
            if w + 1 < W and t[h][w + 1] > a:
                q.append((h, w + 1))
                t[h][w + 1] = a

        if t[Dh][Dw] != INF:
            break

        a += 1
        for h, w in warpq:
            for i in range(max(0, h - 2), min(H, h + 3)):
                ti = t[i]
                for j in range(max(0, w - 2), min(W, w + 3)):
                    if ti[j] > a:
                        ti[j] = a
                        q.append((i, j))
        warpq.clear()

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()

Solution (Python):
from collections import deque


def main():
    from sys import stdin
    readline = stdin.readline

    from builtins import max, min, range

    INF = 10 ** 6

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

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    a = 0
    warpq = []
    while q:
        while q:
            h, w = q.popleft()
            warpq.append((h, w))
            if h - 1 >= 0 and t[h - 1][w] > a:
                q.append((h - 1, w))
                t[h - 1][w] = a
            if h + 1 < H and t[h + 1][w] > a:
                q.append((h + 1, w))
                t[h + 1][w] = a
            if w - 1 >= 0 and t[h][w - 1] > a:
                q.append((h, w - 1))
                t[h][w - 1] = a
            if w + 1 < W and t[h][w + 1] > a:
                q.append((h, w + 1))
                t[h][w + 1] = a

        if t[Dh][Dw] != INF:
            break

        a += 1
        for h, w in warpq:
            for i in range(max(0, h - 2), min(H, h + 3)):
                ti = t[i]
                for j in range(max(0, w - 2), min(W, w + 3)):
                    if ti[j] > a:
                        ti[j] = a
                        q.append((i, j))
        warpq.clear()

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()

Solution (Python):
import sys, math, heapq

def move2(Maps, dists, start, goal, inf):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    queue = []
    heapq.heappush(queue, [0, start[1], start[0]]) 

    while( len(queue) >0 ):
        dist_pos = heapq.heappop(queue)

        dist, x, y = map(int, dist_pos)
        if(dists[y][x] < dist_pos[0]):
            continue
        if(x == goal[1] and y == goal[0]):
            print(dists[y][x])
            return
        Flag = -1 
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                heapq.heappush(queue, [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(queue, [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(queue, [dists[next[1] ][next[0] ], next[0], next[1] ])

    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)




if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) ) 
    goal = list( map(int, input().strip().split() ) ) 
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1

    """
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()
    """
    Maps = [ ]
    for i in range(H):
        Maps.append( input().strip() )
    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] 
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]

    move2(Maps, dists, start, goal, inf)

Solution (Python):
import sys, math, heapq

def move2(Maps, dists, start, goal, inf):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    queue = []
    heapq.heappush(queue, [0, start[1], start[0]]) 

    while( len(queue) >0 ):
        dist_pos = heapq.heappop(queue)

        dist, x, y = map(int, dist_pos)
        if(dists[y][x] < dist_pos[0]):
            continue
        if(x == goal[1] and y == goal[0]):
            print(dists[y][x])
            return
        Flag = -1 
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                heapq.heappush(queue, [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(queue, [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(queue, [dists[next[1] ][next[0] ], next[0], next[1] ])

    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)




if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) ) 
    goal = list( map(int, input().strip().split() ) ) 
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] 
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]

    move2(Maps, dists, start, goal, inf)

Solution (Python):
from collections import deque

def resolve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = []
    for _ in range(H):
        S.append([s for s in input()])

    
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    
    walk = [(-1,0), (0,-1), (1,0), (0,1)]
    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)]

    
    INF = 10**9
    dist = [[INF] * W for _ in range(H)]
    dist[Ch][Cw] = -1

    
    deq = deque()
    deq.append((Ch, Cw, 0))

    while len(deq) > 0:
        (h, w, d) = deq.popleft()
        
        if dist[h][w] < d and dist[h][w] != -1:
            continue
        
        for (dh, dw) in walk:
            nh = h + dh
            nw = w + dw
            
            if (nh < 0) or (nw < 0) or (nh >= H) or (nw >= W):
                continue
            
            if S[nh][nw] == '
                continue
            
            if dist[nh][nw] <= d:
                continue
            dist[nh][nw] = d
            deq.appendleft((nh, nw, d))
        
        for (dh, dw) in warp:
            nh = h + dh
            nw = w + dw
            
            if (nh < 0) or (nw < 0) or (nh >= H) or (nw >= W):
                continue
            
            if S[nh][nw] == '
                continue
            
            if dist[nh][nw] <= d+1:
                continue
            dist[nh][nw] = d+1
            deq.append((nh, nw, d+1))
    ans = dist[Dh][Dw]
    if ans == INF:
        ans = -1
    print(ans)

if __name__ == "__main__":
    resolve()