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):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
def Dijkstra(graph,s):
    INF = 10**9
    dist = [INF]*len(graph)
    dist[s] = 0
    
    
    heap = [(0,s)]
    while heap:
        cost,node = hq.heappop(heap)
        if cost>dist[node]:continue
        for weight,nex in graph[node]:
            d = cost+weight
            if d<dist[nex]:
                dist[nex] = d
                
                hq.heappush(heap,(d,nex))
    for i in range(len(dist)):
        if dist[i] == INF:
            dist[i] = -1
    return dist 

dyx = [(-1,0),(1,0),(0,1),(0,-1)]
INF=10**9
H,W = ma()
ch,cw = ma()
ch-=1;cw-=1
dh,dw=ma()
dh-=1;dw-=1
area= []
for h in range(H):
    area.append(input())

group = [[-1]*W for h in range(H)]
def BFS(sy,sx,idx):
    que = collections.deque()
    que.append((sy,sx))
    group[sy][sx]=idx
    while que:
        h,w = que.popleft()
        for dy,dx in dyx:
            if (0<=h+dy<H )and (0<=w+dx<W):
                if area[h+dy][w+dx] =="." and group[h+dy][w+dx] ==-1:
                    group[h+dy][w+dx] = idx
                    que.append((h+dy,w+dx))


idx = 0
for h in range(H):
    for w in range(W):
        if area[h][w] =="." and group[h][w] ==-1:
            BFS(h,w,idx)
            idx+=1
            

tree = [set() for _ in range(idx)]
dyx2 = [(i,j) for i in range(-2,3) for j in range(-2,3)]
dyx2.remove((0,0))

for h in range(H):
    for w in range(W):
        if area[h][w]=="
            continue
        g = group[h][w]
        for dy,dx in dyx2:
            if (0<=h+dy<H )and (0<=w+dx<W) and (area[h+dy][w+dx]=="."):
                if (g !=group[h+dy][w+dx]):
                    tree[g].add((1,group[h+dy][w+dx]))
                    tree[group[h+dy][w+dx]].add((1,g))
dist = Dijkstra(tree,group[ch][cw])




print(dist[group[dh][dw]])

Solution (Python):
from collections import deque
H,W = list(map(int,input().split()))
start = list(map(lambda x:int(x)-1,input().split()))
goal = list(map(lambda x:int(x)-1,input().split()))
A = [input() for _ in range(H)]
visited = [[0]*W for _ in range(H)]
B = deque([[start[0],start[1],0]])
warp = []
for i in range(-2,3):
    for j in range(-2,3):
            warp.append([i,j])

num = -1

while B:
    y,x,n = B.popleft()
    if visited[y][x] == 1:continue
    if [y,x] == goal:
        num = n
        break
    visited[y][x] = 1
    for dy,dx in [[1,0],[0,1],[-1,0],[0,-1]]:
        if (y+dy<0)|(x+dx<0)|(y+dy>=H)|(x+dx>=W):continue
        if (A[y+dy][x+dx]==".")&(visited[y+dy][x+dx]==0):
            B.appendleft([y+dy,x+dx,n])
    for dy,dx in warp:
        if (y+dy<0)|(x+dx<0)|(y+dy>=H)|(x+dx>=W):continue
        if (A[y+dy][x+dx]==".")&(visited[y+dy][x+dx]==0):
            B.append([y+dy,x+dx,n+1])

print(num)

Solution (Python):
h, w = map(int,input().split())
si, sj = map(int,input().split())
gi, gj = map(int,input().split())
S = [input() for i in range(h)]
n = h * w

si-=1
sj-=1
gi-=1
gj-=1



A = [[-1,0],[1,0],[0,1],[0,-1]]
B = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i!=0 or j!=0) and (not ([i, j] in A)):
            B.append([i, j])















from collections import deque
D = deque()

V = [0] * n
DI = [float("inf")] * n
s = si*w+sj
g = gi*w+gj
DI[s] = 0

D.append([s, 0])

while len(D) > 0:
    d = D.popleft()
    x = d[0]
    we = d[1]
    if V[x] == 0:
        V[x] = 1
        DI[x] = we
        i = x//w
        j = x%w
        for a in A:
            ai = i + a[0]
            aj = j + a[1]
            if 0 <= ai < h and 0 <= aj < w and S[ai][aj] == ".":
                D.appendleft([ai*w+aj, we])
        for a in B:
            ai = i + a[0]
            aj = j + a[1]
            if 0 <= ai < h and 0 <= aj < w and S[ai][aj] == ".":
                D.append([ai*w+aj, we+1])



ans = DI[g]
if DI[g] == float("inf"):
    ans = -1
print(ans)

Solution (Python):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 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)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Solution (Python):
def l():
    return [int(x) for x in input().split()]
def main():
    H,W=l()
    ch,cw=l()
    dh,dw=l()
    ch-=1
    cw-=1
    dw-=1
    dh-=1
    s=[[-2 if x=='
    pad1=[-2,-2]
    pad2=[[-2]*(W+4)]*2
    s=pad2+[pad1+x+pad1 for x in s]+pad2
    move1=[(-1,0),(1,0),(0,-1),(0,1)]
    move2=list(set([(i,j) for i in range(-2,3) for j in range(-2,3)])-set(move1)-set([(0,0)]))
    q1=[(0,ch+2,cw+2)]
    q2=[]
    s[ch+2][cw+2]=0
    def mark(c,h,w):
        if -2<=h<H+2 and -2<=w<W+2 and s[h][w]==-1:
        
            s[h][w]=c
            q1.append((c,h,w))
    while q1:
        
        c,h,w=q1.pop()
        for i,j in move1:
            mark(c,h+i,w+j)
        q2.append((c+1,h,w))
        if not q1:
            for c,h,w in q2:
                for i,j in move2:
                    mark(c,h+i,w+j)
            q2=[]
    ans=s[dh+2][dw+2]
    if ans>=0:
        print(ans)
    else:
        print(-1)
main()

Solution (Python):
import copy
import sys
from collections import deque
H, W = map(int,input().split())
C = list(map(lambda x: int(x) - 1, input().split()))
D = list(map(lambda x: int(x) - 1, input().split()))
S = [input() for _ in range(H)]
check_visited = [[False] * W for _ in range(H)]
dq = deque([[0, C[0], C[1]]])
while dq:
   d, i, j = dq.popleft()
   if [i, j] == D:
      print(d)
      exit()
   if check_visited[i][j]:
      continue
   check_visited[i][j] = True
   for move_h, move_w in [[-1,0], [1,0], [0,-1], [0,1]]:
      new_i = i + move_h
      new_j = j + move_w
      if 0 <= new_i <= H-1 and 0 <= new_j <= W-1 and S[new_i][new_j] == '.' and (not check_visited[new_i][new_j]) :
         dq.appendleft([d, new_i, new_j])
   for move_h in range(-2, 3):
      for move_w in range(-2, 3):
         if [move_h, move_w] == [0, 0]:
            continue
         new_i = i + move_h
         new_j = j + move_w
         if 0 <= new_i <= H-1 and 0 <= new_j <= W-1 and S[new_i][new_j] == '.' and (not check_visited[new_i][new_j]) :
            dq.append([d+1, new_i, new_j])
print(-1)

Solution (Python):
from collections import deque
H,W=map(int,input().split())
C=list(map(int,input().split()))
D=list(map(int,input().split()))
S=[]
ischecked=[[-1]*W for _ in range(H)]
for _ in range(H):
    s=input()
    S.append(s)
walkq=deque()
walkq.append([C[0]-1,C[1]-1])
warpq=deque()

def Walk(h,w):
    if 0<=h<H and 0<=w<W:
        if ischecked[h][w]==-1 and S[h][w]==".":
            walkq.append([h,w])
def Warp(h,w,warp):
    if 0<=h<H and 0<=w<W:
        if ischecked[h][w]==-1 and S[h][w]==".":
            warpq.append([h,w,warp+1])

warp=0
ans=-1
while 1:
    if len(walkq)!=0:
        now=walkq.popleft()
    elif len(warpq)!=0:
        now=warpq.popleft()
        warp=now[2]
    else:
        break
    h=now[0]
    w=now[1]
    if ischecked[h][w]==-1:
        ischecked[h][w]=warp
        Walk(h-1,w)
        Walk(h+1,w)
        Walk(h,w-1)
        Walk(h,w+1)
        for i in range(5):
            for j in range(5):
                Warp(h-2+i,w-2+j,warp)
    if h==D[0]-1 and w==D[1]-1:
        ans=ischecked[h][w]
        break
print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
moveA_q = deque()
moveB_q = deque()
moveA_q.append([sW, sH])
moveB_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while moveA_q or moveB_q:
    if scores[gH][gW] != float('inf'):
        break
    
    while moveA_q:
        x, y = moveA_q.pop()
        moveB_q.append([x, y])
        for dx, dy in zip(dx_list, dy_list):
            nx, ny = x + dx, y + dy
            if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '
                continue
            
            if scores[ny][nx] > scores[y][x]:
                scores[ny][nx] = scores[y][x]
                moveA_q.append([nx, ny])
                

    
    while moveB_q:
        x, y = moveB_q.pop()
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '
                    continue
                
                if scores[ny][nx] > scores[y][x]:
                    moveA_q.append([nx, ny])
                    scores[ny][nx] = scores[y][x] + 1


if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])

Solution (Python):
import copy
import sys
from collections import deque
H, W = map(int,input().split())
C = list(map(lambda x: int(x) - 1, input().split()))
D = list(map(lambda x: int(x) - 1, input().split()))
S = [input() for _ in range(H)]
check_visited = [[False] * W for _ in range(H)]
dq = deque([[0, C[0], C[1]]])
while dq:
   d, i, j = dq.popleft()
   if [i, j] == D:
      print(d)
      exit()
   if check_visited[i][j]:
      continue
   check_visited[i][j] = True
   for move_h, move_w in [[-1,0], [1,0], [0,-1], [0,1]]:
      new_i = i + move_h
      new_j = j + move_w
      if 0 <= new_i <= H-1 and 0 <= new_j <= W-1 and S[new_i][new_j] == '.' and (not check_visited[new_i][new_j]) :
         dq.appendleft([d, new_i, new_j])
   for move_h in range(-2, 3):
      for move_w in range(-2, 3):
         if [move_h, move_w] == [0, 0]:
            continue
         new_i = i + move_h
         new_j = j + move_w
         if 0 <= new_i <= H-1 and 0 <= new_j <= W-1 and S[new_i][new_j] == '.' and (not check_visited[new_i][new_j]) :
            dq.append([d+1, new_i, new_j])
print(-1)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
moveA_q = deque()
moveB_q = deque()
moveA_q.append([sW, sH])
moveB_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while moveA_q or moveB_q:
    if scores[gH][gW] != float('inf'):
        break
    
    while moveA_q:
        x, y = moveA_q.pop()
        moveB_q.append([x, y])
        for dx, dy in zip(dx_list, dy_list):
            nx, ny = x + dx, y + dy
            if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '
                continue
            
            if scores[ny][nx] > scores[y][x]:
                scores[ny][nx] = scores[y][x]
                moveA_q.append([nx, ny])


    
    while moveB_q:
        x, y = moveB_q.pop()
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '
                    continue
                
                if scores[ny][nx] > scores[y][x]:
                    moveA_q.append([nx, ny])
                    scores[ny][nx] = scores[y][x] + 1


if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])

Solution (Python):
def l():
    return [int(x) for x in input().split()]
def main():
    H,W=l()
    ch,cw=l()
    dh,dw=l()
    ch-=1
    cw-=1
    dw-=1
    dh-=1
    s=[[-2 if x=='
    pad1=[-2,-2]
    pad2=[[-2]*(W+4)]*2
    s=pad2+[pad1+x+pad1 for x in s]+pad2
    move1=[(-1,0),(1,0),(0,-1),(0,1)]
    move2=list(set([(i,j) for i in range(-2,3) for j in range(-2,3)])-set(move1)-set([(0,0)]))
    q1=[(0,ch+2,cw+2)]
    q2=[]
    s[ch+2][cw+2]=0
    def mark(c,h,w):
        
        if s[h][w]==-1:
            s[h][w]=c
            q1.append((c,h,w))
    while q1:
        
        c,h,w=q1.pop()
        for i,j in move1:
            mark(c,h+i,w+j)
        q2.append((c+1,h,w))
        if not q1:
            for c,h,w in q2:
                for i,j in move2:
                    mark(c,h+i,w+j)
            q2=[]
    ans=s[dh+2][dw+2]
    if ans>=0:
        print(ans)
    else:
        print(-1)
main()

Solution (Python):
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
moveA_q = deque()
moveB_q = deque()
moveA_q.append([sW, sH])
moveB_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while moveA_q:
    if scores[gH][gW] != float('inf'):
        break
    
    while moveA_q:
        x, y = moveA_q.pop()
        moveB_q.append([x, y])
        for dx, dy in zip(dx_list, dy_list):
            nx, ny = x + dx, y + dy
            if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '
                continue
            
            if scores[ny][nx] > scores[y][x]:
                scores[ny][nx] = scores[y][x]
                moveA_q.append([nx, ny])
                

    
    while moveB_q:
        x, y = moveB_q.pop()
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '
                    continue
                
                if scores[ny][nx] > scores[y][x]:
                    moveA_q.append([nx, ny])
                    scores[ny][nx] = scores[y][x] + 1


if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])

Solution (Python):
from collections import deque


def solve(h, w, ch, cw, dh, dw, s_list):

    s_arr = [[False] * (w + 4) for _ in range(h + 4)]
    for i, s in enumerate(s_list):
        for j in range(w):
            if s[j] == ".":
                s_arr[i + 2][j + 2] = True

    done_arr = [[False] * (w + 4) for _ in range(h + 4)]

    
    queue = deque()
    res = -1
    
    queue.append((0, ch + 1, cw + 1))
    
    while len(queue):
        d, i, j = queue.popleft()
        if done_arr[i][j]:
            continue
        done_arr[i][j] = True
        
        if i == dh + 1 and j == dw + 1:
            res = d
            
            break
        for i_ in range(i - 2, i + 3):
            for j_ in range(j - 2, j + 3):
                if not done_arr[i_][j_] and s_arr[i_][j_]:
                    diff = abs(i_ - i) + abs(j_ - j)
                    if diff > 1:
                        queue.append((d + 1, i_, j_))
                    else:
                        queue.appendleft((d, i_, j_))
    
    return res


def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    s_list = []
    for i in range(h):
        s = input()
        s_list.append(s)
    res = solve(h, w, ch, cw, dh, dw, s_list)
    print(res)


def test():
    assert solve(4, 4, 1, 1, 4, 4, ["..
    assert solve(4, 4, 1, 4, 4, 1, [".
    assert solve(4, 4, 2, 2, 3, 3, ["....", "....", "....", "...."]) == 0
    assert solve(4, 5, 1, 2, 2, 5, ["


def test_large():
    assert solve(1000, 1000, 1, 1, 1000, 1000, ["." * 1000 for _ in range(1000)]) == 0


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

Solution (Python):



def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

h,w = mp()
ch, cw = mp()
dh,dw = mp()
ch += 1
cw += 1
dh += 1
dw += 1
grid = []
grid.append(["
grid.append(["
ans_grid = []
for i in range(h):
    u = ["
    a = list(input())
    for j in range(w):
        u.append(a[j])
    u.append("
    u.append("
    grid.append(u)
grid.append(["
grid.append(["

for i in range(h+4):
    ans_grid.append([int(1e6+2)]*(w+4))



from collections import deque
def bfs(x,y):
    q = deque([])
    used = set()
    q.append((x,y))
    used.add((x,y))
    ans_grid[x][y] = 0
    while q:
        here = q.popleft()
        move = [(here[0]-1, here[1]),
                (here[0], here[1]-1),
                (here[0], here[1]+1),
                (here[0]+1, here[1])]
        warp = [(here[0]-2, here[1]-2), (here[0]-2, here[1]-1), (here[0]-2, here[1]), (here[0]-2, here[1]+1), (here[0]-2, here[1]+2),
                (here[0]-1, here[1]-2), (here[0]-1, here[1]-1), (here[0]-1, here[1]+1), (here[0]-1, here[1]+2),
                (here[0], here[1]-2), (here[0], here[1]+2),
                (here[0]+1, here[1]-2), (here[0]+1, here[1]-1), (here[0]+1, here[1]+1), (here[0]+1, here[1]+2),
                (here[0]+2, here[1]-2), (here[0]+2, here[1]-1), (here[0]+2, here[1]), (here[0]+2, here[1]+1), (here[0]+2, here[1]+2)]
        for i in range(len(warp)):
            u = warp[i][0]
            v = warp[i][1]
            if grid[u][v] == "." and ans_grid[u][v] > ans_grid[here[0]][here[1]]+1:
                ans_grid[u][v] = min(ans_grid[u][v], ans_grid[here[0]][here[1]]+1)
                q.append((u,v))
        for i in range(len(move)):
            u = move[i][0]
            v = move[i][1]
            if (move[i] not in used or ans_grid[u][v] > ans_grid[here[0]][here[1]]) and grid[u][v] == ".":
                ans_grid[u][v] = min(ans_grid[here[0]][here[1]], ans_grid[u][v])
                q.appendleft((u,v))
                used.add((u,v))

bfs(ch,cw)
ans = ans_grid[dh][dw]

if ans == int(1e6+2):
    print(-1)
else:
    print(ans)

Solution (Python):
from collections import deque
inf=float("inf")


def BFS():
    D=[[inf for _ in range(W)] for _ in range(H)]
    queue=deque()
    queue.append([Cx-1,Cy-1,0])
    D[Cx-1][Cy-1]=0

    while len(queue)>0:
        x,y,cnt=queue.popleft()
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<H and 0<=Y<W:
                if S[X][Y]=="." and D[X][Y]>cnt:
                    D[X][Y]=cnt
                    queue.appendleft([X,Y,cnt])
        for X in range(max(0,x-2),min(H,x+3)):
            for Y in range(max(0,y-2),min(W,y+3)):
                if S[X][Y]=="." and D[X][Y]>cnt+1:
                    D[X][Y]=cnt+1
                    queue.append([X,Y,cnt+1])

    return D[Dx-1][Dy-1]


H,W=map(int,input().split())
Cx,Cy=map(int,input().split())
Dx,Dy=map(int,input().split())
S=[list(input()) for _ in range(H)]

ans=BFS()
print(ans if ans!=inf else -1)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
moveA_q = deque()
moveB_q = deque()
moveA_q.append([sW, sH])
moveB_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while moveA_q:
    if scores[gH][gW] != float('inf'):
        break
    
    x, y = moveA_q.pop()
    moveB_q.append([x, y])
    for dx, dy in zip(dx_list, dy_list):
        nx, ny = x + dx, y + dy
        if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '
            continue
        if scores[ny][nx] == float('inf'):
        
            scores[ny][nx] = scores[y][x]
            moveA_q.append([nx, ny])

    if not moveA_q:
        
        while moveB_q:
            x, y = moveB_q.pop()
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    nx, ny = x + dx, y + dy
                    if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '
                        continue
                    if scores[ny][nx] == float('inf'):
                    
                        moveA_q.append([nx, ny])
                        scores[ny][nx] = scores[y][x] + 1


if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])

Solution (Python):
from collections import deque

H,W = map(int,input().split())
c_h, c_w = map(int,input().split())
d_h, d_w = map(int,input().split())

c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1

s = [list(input()) for _ in range(H)]



q = deque()
q.append((c_h,c_w))

INF = 1e9


dist = [[INF for _ in range(W)] for __ in range(H)]

dist[c_h][c_w] = 0

dh = (0,1,0,-1)
dw = (1,0,-1,0)

while(len(q) > 0):
    
    now = q.popleft()
    now_h,now_w = now

    d = dist[now_h][now_w]

    
    for di in range(4):
        next_h = now_h + dh[di]
        next_w = now_w + dw[di]

        if (next_h<0 or next_h>=H or next_w<0 or next_w>=W): continue
        if (s[next_h][next_w] == '
        if dist[next_h][next_w] <= d: continue

        
        dist[next_h][next_w] = d

        
        q.appendleft((next_h,next_w))

    
    for ew in range(-2,3):
        for eh in range(-2,3):
            next_h = eh + now_h
            next_w = ew + now_w

            if (next_h<0 or next_h>=H or next_w<0 or next_w>=W): continue
            if (s[next_h][next_w] == '
            if dist[next_h][next_w] <= d+1: continue

            dist[next_h][next_w] = d+1
            q.append((next_h,next_w))

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

Solution (Python):
from collections import deque
H, W= map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
A = []
for i in range(H):
  A.append([])
  s = input()
  for j in range(W):
    if s[j] == '.':
      A[-1].append(0)
    else:
      A[-1].append(1)
P = [[1e6 for i in range(W)] for j in range(H)]
P[Ch][Cw] = 0
D = deque([[Ch, Cw]])
while len(D):
  d = D.pop()
  for i in range(-2, 3):
    for j in range(-2, 3):
      if 0 <= d[0]+i < H and 0 <= d[1]+j < W and A[d[0]+i][d[1]+j] == 0:
        if (i + j == 1 or i + j == -1) and i*j == 0 and P[d[0]][d[1]] < P[d[0]+i][d[1]+j]:
          D.append([d[0]+i, d[1]+j])
          P[d[0]+i][d[1]+j] = P[d[0]][d[1]]
        elif P[d[0]][d[1]]+1 < P[d[0]+i][d[1]+j]:
          D.appendleft([d[0]+i, d[1]+j])
          P[d[0]+i][d[1]+j] = P[d[0]][d[1]] + 1
if P[Dh][Dw] == 1e6:
  print(-1)
else:
  print(P[Dh][Dw])

Solution (Python):
def main():
    H, W = map(int, input().split())

    y, x = map(int, input().split())
    start = (x+1, y+1)

    y, x = map(int, input().split())
    goal = (x+1, y+1)

    dist_table = [[-2] * (W+4)]
    dist_table.append([-2] * (W+4))
    for _ in range(H):
        row = '
        row = [-1 if c == '.' else -2 for c in row]
        dist_table.append(row)
    dist_table.append([-2] * (W+4))
    dist_table.append([-2] * (W+4))



    sx, sy = start
    dist_table[sy][sx] = 0

    move1 = ((-1, 0), (1, 0), (0, 1), (0, -1))
    move2 = ((-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))

    queue1 = [start]
    queue2 = []

    while queue1:
        now_x, now_y = queue1.pop()
        if (now_x, now_y) == goal:
            break
        queue2.append((now_x, now_y))
        dist = dist_table[now_y][now_x]
        for dx, dy in move1:
            tx, ty = now_x + dx, now_y + dy
            if dist_table[ty][tx] == -1:
                dist_table[ty][tx] = dist
                queue1.append((tx, ty))
        if len(queue1) == 0:
            while queue2:
                now_x, now_y = queue2.pop()
                dist = dist_table[now_y][now_x]
                for dx, dy in move2:
                    tx, ty = now_x + dx, now_y + dy
                    if dist_table[ty][tx] == -1:
                        dist_table[ty][tx] = dist + 1
                        queue1.append((tx, ty))
    gx, gy = goal
    print(dist_table[gy][gx])

if __name__ == '__main__':
    main()

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 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())
tizu=[]
d=deque()
d.appendleft([ch,cw])
cost=[[-1 for i in range(w)]for j in range(h)]
dx=[1,0,-1,0,-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
dy=[0,1,0,-1,-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
for i in range(h):
    tizu.append(input())
cost[ch][cw]=0
while(d):
    x,y=d.popleft()
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        
        if(nx<0 or ny<0 or nx>=h or ny>=w):
            continue
        if(cost[nx][ny]>-1 and cost[nx][ny]<=cost[x][y]):
            continue
        if(tizu[nx][ny]=='.'):
            cost[nx][ny]=cost[x][y]
            d.appendleft([nx,ny])
    
    for i in range(4,24):
        nx=x+dx[i]
        ny=y+dy[i]
        if(nx<0 or ny<0 or nx>=h or ny>=w):
            continue
        if(cost[nx][ny]>-1):
            continue
        if(tizu[nx][ny]=='.'):
            cost[nx][ny]=cost[x][y]+1
            d.append([nx,ny])

print(cost[dh][dw])

Solution (Python):
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [input() for i in range(H)]

queue = deque()
queue.append((Ch-1, Cw-1, 0))
inf = float("inf")
table = [[inf] * W for i in range(H)]
table[Ch-1][Cw-1] = 0
walk_move = ((-1, 0), (0, -1), (1, 0), (0, 1))
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i, j])

while queue:
  x, y, cost = queue.popleft()
  for i,j in walk_move:
    dx = x+i
    dy = y+j
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost:
      queue.appendleft((dx, dy, cost))
      table[dx][dy] = cost
  for k,l in magic_move:
    dx = x+k
    dy = y+l
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost+1:
      queue.append((dx, dy, cost+1))
      table[dx][dy] = cost+1

ans = table[Dh-1][Dw-1]
if ans == inf:
  print("-1")
else:
  print(table[Dh-1][Dw-1])

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 = [(1,0), (0,1), (-1,0), (0,-1)] 
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] != "
            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] != "
            path[nx][ny] = s+1
            q.append((nx, ny, s+1))

ans = path[dh][dw] if path[dh][dw] < INF else -1
print(ans)