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

imput = sys.stdin.readline

h,w = map(int,input().split())
sy,sx= map(int,input().split())
gy,gx= map(int,input().split())
S=[]



for i in range(h):
    S.append(input())

walk = [[1,0],[-1,0],[0,1],[0,-1]]
move = [[x,y] for x in range(-2,3) for y in range(-2,3) if [x,y] not in walk + [[0,0]]] 

dist = [[9999999]*w for i in range(h)]


q=deque()
q.append((sx-1,sy-1,0))
dist[sy-1][sx-1]=0
goaled = 0
endwarp=0

while len(q):
    endwarp=0
    
    x,y,d = q.popleft()
    




    

    for i in walk:
        if 0<=x+i[0]<w and 0<=y+i[1]<h and S[y+i[1]][x+i[0]]!="

                    dist[y+i[1]][x+i[0]] = d
                    q.appendleft((x+i[0],y+i[1],d+0))

    for i in move:
        if 0<=x+i[0]<w and 0<=y+i[1]<h and S[y+i[1]][x+i[0]]!="

                    dist[y+i[1]][x+i[0]] = d+1
                    q.append((x+i[0],y+i[1],d+1))
                        
                        
                         
    
    

if dist[gy-1][gx-1]==9999999:
    print(-1)
    
else:
    print(dist[gy-1][gx-1])

Solution (Python):
import heapq
import numpy as np
from numba import njit,i8,b1

h,w = map(int,input().split())
sh,sw = map(int,input().split())
gh,gw = map(int,input().split())
s = np.array([list(input()) for _ in range(h)]) == "

@njit(i8(i8,i8,i8,i8,i8,i8,b1[:,:]))
def solve(h,w,sh,sw,gh,gw,s):

    sh-=1; sw-=1; gh-=1; gw-=1;

    INF = 10**7
    dist = [[INF]*w for _ in range(h)]
    dist[sh][sw] = 0
    q = [(0,sh,sw)]
    while q:

        d,vsh,vsw = heapq.heappop(q)

        for dh in range(-2,3):
            for dw in range(-2,3):
                newh = vsh+dh
                neww = vsw+dw
                if newh<0 or h<=newh or neww<0 or w<=neww: continue
                if dh == 0 and dw==0: continue
                if s[newh][neww] : continue


                if abs(dh)+abs(dw)==1:
                    if dist[newh][neww] > d:
                        dist[newh][neww] = d
                        if newh == gh and neww == gw:
                            return d
                        heapq.heappush(q,(d,newh,neww))
                else:
                    if dist[newh][neww] > d+1:
                        dist[newh][neww] = d+1
                        heapq.heappush(q,(d+1,newh,neww))
    if dist[gh][gw] == INF:
        return -1
    else: return dist[gh][gw]
        
print(solve(h,w,sh,sw,gh,gw,s))

Solution (Python):
from collections import deque
 
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
stage = ['
stage = ['
queue = deque([(ch,cw)])
check = [[1]*(w+2) for i in range(h+2)]
searched_temp = [(ch,cw)]
count = 0
 
while True:
  searched = searched_temp
  
  while len(queue):
    v = queue.popleft()
    if v == (dh,dw):
      print(count)
      exit()
 
    if stage[v[0]-1][v[1]] == '.' and check[v[0]-1][v[1]]:
      queue.append((v[0]-1,v[1]))
      check[v[0]-1][v[1]] = 0
      searched.append((v[0]-1,v[1]))
    if stage[v[0]+1][v[1]] == '.' and check[v[0]+1][v[1]]:
      queue.append((v[0]+1,v[1]))
      check[v[0]+1][v[1]] = 0
      searched.append((v[0]+1,v[1]))
    if stage[v[0]][v[1]-1] == '.' and check[v[0]][v[1]-1]:
      queue.append((v[0],v[1]-1))
      check[v[0]][v[1]-1] = 0
      searched.append((v[0],v[1]-1))
    if stage[v[0]][v[1]+1] == '.' and check[v[0]][v[1]+1]:
      queue.append((v[0],v[1]+1))
      check[v[0]][v[1]+1] = 0
      searched.append((v[0],v[1]+1))
  
  count += 1
  searched_temp = []
  for s in searched:
    for i in range(-2,3):
      for j in range(-2,3):
        y = s[0] + i
        x = s[1] + j
        if 1 <= y and y <= h and 1 <= x and x <= w:
          if stage[y][x] == '.' and check[y][x]:
            check[y][x] = 0
            queue.append((y,x))
            searched_temp.append((y,x))
          
  if len(queue) == 0:
    print(-1)
    break

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

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

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

inf = int(1e9)
dist = [[inf for j in range(w)] for i in range(h)]
dist[ch][cw] = 0

q = deque()
q.append([ch,cw])

while len(q) != 0:
    i, j = map(int, q.popleft())
    d = dist[i][j]
    
    for v in range(4):
        ni = i + dx[v]
        nj = j + dy[v]

        if ni < 0 or ni >= h or nj < 0 or nj >= w:
            continue
        
        if s[ni][nj] == "
            continue

        if dist[ni][nj] <= d:
            continue
        
        dist[ni][nj] = d
        q.appendleft([ni, nj])
    
    for ei in range(-2, 3):
        for ej in range(-2, 3):
            ni = i + ei
            nj = j + ej

            if ni < 0 or ni >= h or nj < 0 or nj >= w:
                continue
        
            if s[ni][nj] == "
                continue

            if dist[ni][nj] <= d+1:
                continue

            dist[ni][nj] = d+1
            q.append([ni, nj])

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

Solution (Python):
from collections import deque
import math

def solve3(s_flag,h,w,goal_h,goal_w,que):
    while True:
        visited=set()
        while que:
            ch,cw=que.popleft()
            visited.add((ch,cw))
            
            now=s_flag[ch][cw]
            for d_h,d_w in [(1,0),(0,1),(0,-1),(-1,0)]:
                
                if ch+d_h<0 or h-1<ch+d_h:
                    continue
                if cw+d_w<0 or w-1<cw+d_w:
                    continue
                
                dest=s_flag[ch+d_h][cw+d_w]
                if dest!='
                    if dest>now:
                        s_flag[ch+d_h][cw+d_w]=now
                        que.append([ch+d_h,cw+d_w])
        jumping=set()
        for ch,cw in visited:
            now=s_flag[ch][cw]
            for d_h,d_w in [(1,0),(0,1),(0,-1),(-1,0)]:
                jump=[  (d_h+d_w,d_w+d_h),
                        (d_h-d_w,d_w-d_h),
                        (d_h*2,d_w*2),
                        (d_h*2+d_w,d_w*2+d_h),
                        (d_h*2-d_w,d_w*2-d_h),
                        (d_h*2+d_w*2,d_w*2+d_h*2),
                        (d_h*2-d_w*2,d_w*2-d_h*2)]
                for jump_h,jump_w in jump:
                    if ch+jump_h<0 or h-1<ch+jump_h:
                        continue
                    if cw+jump_w<0 or w-1<cw+jump_w:
                        continue
                    jumping.add((ch+jump_h,cw+jump_w))
        if len(jumping)==0:
            break
        for d_jump_h,d_jump_w in jumping:
            
            dest_jump=s_flag[d_jump_h][d_jump_w]
            if dest_jump!='
                s_flag[d_jump_h][d_jump_w]=now+1
                que.append([d_jump_h,d_jump_w])

    
    
    return s_flag[goal_h][goal_w]

def main():
    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=[input() for i in range(h)]
    
    
    
    
    
    
    
    
    
    
    
    s_flag=[[math.inf if s[i][j]=='.' else '
    s_flag[ch][cw]=0
    que=deque([[ch,cw]])
    ans=solve3(s_flag,h,w,dh,dw,que)
    if ans==math.inf:
        ans=-1
    return ans

if __name__=='__main__':
    ans=main()
    print(ans)

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())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())

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

que = deque([(0,Ch-1,Cw-1)])
adjecents = [(1,0),(0,1),(-1,0),(0,-1)]
while que:
    step,h,w = que.popleft()
    if h == Dh-1 and w == Dw-1:
        print(step)
        exit()
    if maze[h][w] == "
        continue
    else:
        maze[h][w] = "
        for a,b in adjecents:
            x = h + a
            y = w + b
            if 0 <= x < H and 0<= y < W:
                if maze[x][y] == ".":
                    que.appendleft((step,x,y))
                else:
                    for i in range(-2,3):
                        for j in range(-2,3):
                            x = h + i
                            y = w + j
                            if 0 <= x < H and 0<= y < W and maze[x][y] == ".":
                                que.append((step+1,x,y))

print(-1)

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

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

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)+1, input().split())
gh, gw = map(lambda x:int(x)+1, input().split())

wall = [0]*(H+4)
wall[0] = [True]*(W+4)
wall[1] = [True]*(W+4)
wall[H+2] = [True]*(W+4)
wall[H+3] = [True]*(W+4)
for h in range(2,H+2):
  wall[h] = [True]*2 + [s=='
wall = np.array(wall)
print(main(wall, sh, sw, gh, gw))

Solution (Python):
from collections import deque


def solve():
    H, W = map(int, input().split())
    CH, CW = map(int, input().split())
    DH, DW = map(int, input().split())
    S = ["
    for i in range(2):
        S.insert(0, "
        S.append("

    inf = int(1e9)
    cost = [[inf for _ in range(W+4)] for _ in range(H+4)]
    cost0 = deque()
    ans = -1

    cost0.append((CH+1, CW+1, 0))
    cost[CH+1][CW+1] = 0

    move = [(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)]+move]

    cost1 = deque()

    while cost0:
        h, w, c = cost0.popleft()
        cost1.append((h, w, c))

        for i, j in move:
            dh = h+i
            dw = w+j
            if S[dh][dw] == "." and c < cost[dh][dw]:
                cost[dh][dw] = c
                cost0.appendleft((dh, dw, cost[dh][dw]))

        if len(cost0) == 0:
            while cost1:
                h, w, c = cost1.popleft()
                for i, j in warp:
                    dh = h+i
                    dw = w+j
                    if S[dh][dw] == "." and c+1 < cost[dh][dw]:
                        cost[dh][dw] = c+1
                        cost0.append((dh, dw, cost[dh][dw]))

        if cost[DH+1][DW+1] != inf:
            ans = cost[DH+1][DW+1]

    print(ans)


if __name__ == "__main__":
    solve()

Solution (Python):
import sys
read = sys.stdin.readline
import time
from heapq import heappush, heappop, heapify
import math
import itertools as it
from collections import deque 


def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()


H, W = inpl()
ch, cw = inpl()
dh, dw = inpl()
ch -= 1
cw -= 1
dh -= 1
dw -= 1

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

dist = []
INF = 1001001001
for i in range(H):
    dist.append([INF for i in range(W)])

q = deque([])
q.append((ch, cw))
dist[ch][cw] = 0
while q:
    h, w = q.popleft()
    
    for i, j in ((1,0),(-1,0),(0,1),(0,-1)):
        if not 0 <= h + i < H:
            continue
        if not 0 <= w + j < W:
            continue
        if S[h+i][w+j] == '
            continue
        if dist[h][w] < dist[h+i][w+j]:
            dist[h+i][w+j] = dist[h][w]
            q.appendleft((h+i, w+j))
    
    for i in range(-2, 3):
        for j in range(-2, 3):
            if not 0 <= h + i < H:
                continue
            if not 0 <= w + j < W:
                continue
            if S[h+i][w+j] == '
                continue
            if dist[h][w] + 1 < dist[h+i][w+j]:
                dist[h+i][w+j] = dist[h][w] + 1
                q.append((h+i, w+j))

print(dist[dh][dw] if dist[dh][dw] != INF else -1)




end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

l = [[1 if i=="
q = deque([(0, (Ch-1, Cw-1))])
INF = 10**12
costs = [[INF]*W for _ in range(H)]
costs[Ch-1][Cw-1] = 0

while q:
    cost, pos = q.popleft()
    h, w = pos
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if dh==0 and dw==0:
                continue
            hh, ww = h+dh, w+dw
            if not (0<=hh<H and 0<=ww<W):
                continue
            if l[hh][ww]:
                continue
            
            if ((abs(dh)==1 and dw==0) or (dh==0 and abs(dw)==1)) and costs[hh][ww] > costs[h][w]:
                costs[hh][ww] = costs[h][w]
                q.appendleft((cost, (hh, ww)))
            elif costs[hh][ww] > costs[h][w]+1:
                costs[hh][ww] = costs[h][w]+1
                q.append((cost+1, (hh, ww)))

ans = costs[Dh-1][Dw-1]
print(ans if ans!=INF else -1)

Solution (Python):
from collections import deque
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = [[1 if i=="
    q = deque([(0, (Ch-1, Cw-1))])
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch-1][Cw-1] = 0

    while q:
        cost, pos = q.popleft()
        h, w = pos
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                if dh==0 and dw==0:
                    continue
                hh, ww = h+dh, w+dw
                if not (0<=hh<H and 0<=ww<W):
                    continue
                if l[hh][ww]:
                    continue
                
                if ((abs(dh)==1 and dw==0) or (dh==0 and abs(dw)==1)) and costs[hh][ww] > costs[h][w]:
                    costs[hh][ww] = costs[h][w]
                    q.appendleft((cost, (hh, ww)))
                elif costs[hh][ww] > costs[h][w]+1:
                    costs[hh][ww] = costs[h][w]+1
                    q.append((cost+1, (hh, ww)))

    ans = costs[Dh-1][Dw-1]
    print(ans if ans!=INF else -1)


solve()

Solution (Python):
from collections import deque
from itertools import product
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = [[1 if i=="
    q = deque([(0, (Ch-1, Cw-1))])
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch-1][Cw-1] = 0

    while q:
        cost, pos = q.popleft()
        h, w = pos

        for dh, dw in product(range(-2,3), repeat=2):
            if dh==0 and dw==0:
                continue
            hh, ww = h+dh, w+dw
            if not (0<=hh<H and 0<=ww<W):
                continue
            if l[hh][ww]:
                continue
            
            if ((abs(dh)==1 and dw==0) or (dh==0 and abs(dw)==1)) and costs[hh][ww] > costs[h][w]:
                costs[hh][ww] = costs[h][w]
                q.appendleft((cost, (hh, ww)))
            elif costs[hh][ww] > costs[h][w]+1:
                costs[hh][ww] = costs[h][w]+1
                q.append((cost+1, (hh, ww)))

    ans = costs[Dh-1][Dw-1]
    print(ans if ans!=INF else -1)


solve()

Solution (Python):
from collections import deque
from itertools import product
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = [[1 if i=="
    q = deque([(0, (Ch-1, Cw-1))])
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch-1][Cw-1] = 0

    while q:
        cost, pos = q.popleft()
        h, w = pos

        for dh, dw in product(range(-2,3), repeat=2):
            hh, ww = h+dh, w+dw
            if not (0<=hh<H and 0<=ww<W):
                continue
            if l[hh][ww]:
                continue
            
            if ((abs(dh)==1 and dw==0) or (dh==0 and abs(dw)==1)) and costs[hh][ww] > costs[h][w]:
                costs[hh][ww] = costs[h][w]
                q.appendleft((cost, (hh, ww)))
            elif costs[hh][ww] > costs[h][w]+1:
                costs[hh][ww] = costs[h][w]+1
                q.append((cost+1, (hh, ww)))

    ans = costs[Dh-1][Dw-1]
    print(ans if ans!=INF else -1)


solve()

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(2 * H * W + 100, np.int64)
    dist[S] = 0
    deq[H * W], l, r = S, H * W, H * W + 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
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = [[1 if i=="
    q = deque([(0, (Ch-1, Cw-1))])
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch-1][Cw-1] = 0

    while q:
        cost, pos = q.popleft()
        h, w = pos
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                hh, ww = h+dh, w+dw
                if not (0<=hh<H and 0<=ww<W):
                    continue
                if l[hh][ww]:
                    continue
                
                if ((abs(dh)==1 and dw==0) or (dh==0 and abs(dw)==1)) and costs[hh][ww] > costs[h][w]:
                    costs[hh][ww] = costs[h][w]
                    q.appendleft((cost, (hh, ww)))
                elif costs[hh][ww] > costs[h][w]+1:
                    costs[hh][ww] = costs[h][w]+1
                    q.append((cost+1, (hh, ww)))

    ans = costs[Dh-1][Dw-1]
    print(ans if ans!=INF else -1)


solve()

Solution (Python):
from collections import deque

INF = 10**6
walk_area=[(1,0), (0,1), (-1,0), (0,-1)]
warp_area=[]
for i in range(-2, 3):
    for j in range(-2, 3):
        warp_area.append((i, j))
    
def walk(a, b, num, S, COST):
    m = S[a][b] 
    if m == '.':
        COST[a][b] = num
        
        return
    else:
        
        return

def warp(x,y,num, S, COST, d):
    m = S[x][y]
    if m == '.':
        COST[x][y] = num
        d.append([x, y])
        return
    if m == '
        return
    S[x][y] = min(num, m)
    return

def main():
    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())
    S = ['
    S.append('
    for i in range(h):
        S.append('
    S.append('
    S.append('
    
    
    COST = [[INF for i in range(w+4)] for j in range(h+4)]
    COST[ch][cw] = 0

    d = deque([[ch,cw,0]])
    d2 = deque()
    while len(d) > 0:
        t = d.popleft()
        d2.append(t)
        x = t[0]
        y = t[1]
        num = t[2] 
        for dx, dy in walk_area:
            X = x + dx
            Y = y + dy
            if S[X][Y] == '
                continue
        
            COST[X][Y] = num
            d.append([X, Y, num])
        if not d:
            while len(d2) > 0:
                x, y, num = d2.popleft()
                for dx, dy in warp_area:
                    X = x + dx
                    Y = y + dy
                    if S[X][Y] == '
                        continue
                    
                    COST[X][Y] = num + 1
                    d.append([X, Y, num + 1])
    
    
    if COST[dh][dw] == 10**6:
        print(-1)
    else:
        print(COST[dh][dw])
    return

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, deque
import sys
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(input())
ans = 0
seen = [[-1]*W for _ in range(H)]
vec = [[1, 0], [0, 1], [-1, 0], [0, -1]]
v2 = [[1, 1], [-1, 1], [-1, -1], [1, -1], [2, 1], [1, 2], [-1, 2], [2, -1], [-2, 1], [1, -2], [-1, -2], [-2, -1], [2, 0], [0, 2], [-2, 0], [0, -2], [2, 2], [2, -2], [-2, -2], [-2, 2]]
queue = deque()
q = deque()
queue.append([Ch-1, Cw-1])
q.append([Ch-1, Cw-1])
seen[Ch-1][Cw-1]=0

while queue:
    while queue:
        l = queue.popleft()
        q.append(l)
        h, w = l[0], l[1]
        for ll in vec:
            
            if h+ll[0]>=H or h+ll[0]<0 or w+ll[1]>=W or w+ll[1]<0:
                continue
            
            if S[h+ll[0]][w+ll[1]]=="
                continue
            
            if seen[h+ll[0]][w+ll[1]]!=-1:
                continue
            queue.append([h+ll[0], w+ll[1]])
            q.append([h+ll[0], w+ll[1]])
            seen[h+ll[0]][w+ll[1]]=ans
    ans+=1
    
    while q:
        l = q.popleft()
        h, w = l[0], l[1]
        for z in v2:
            
            if h+z[0]>=H or h+z[0]<0 or w+z[1]>=W or w+z[1]<0:
                continue
            
            if S[h+z[0]][w+z[1]]=="
                continue
            
            if seen[h+z[0]][w+z[1]]!=-1:
                continue
            queue.append([h+z[0], w+z[1]])
            seen[h+z[0]][w+z[1]]=ans
print(seen[Dh-1][Dw-1])

Solution (Python):
from collections import deque
 

H,W=map(int,input().split())
Ch,Cw=[int(x)-1 for x in input().split()]
Dh,Dw=[int(x)-1 for x in input().split()]
maze=[input() for i in range(H)]
 
dirs=[-2,-1,0,1,2] 


dist=[[float('inf')]*W for _ in range(H)] 
dist[Ch][Cw]=0
queue=deque()
queue.append((0,Ch,Cw)) 
arrive=False 

while queue:
    k,i,j=queue.popleft()
    if k>dist[i][j]:
        continue
    if i==Dh and j==Dw:
        arrive=True
        break
    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 maze[ni][nj]=='
                continue
            if k<dist[ni][nj]: 
                if abs(di)+abs(dj)==1: 
                    nk=k
                    dist[ni][nj]=nk
                    queue.appendleft((nk,ni,nj))
                else: 
                    nk=k+1
                    dist[ni][nj]=nk
                    queue.append((nk,ni,nj))   
if arrive:
    ans=dist[Dh][Dw]
else:
    ans=-1
print(ans)

Solution (Python):
from collections import deque
 

H,W=map(int,input().split())
Ch,Cw=[int(x)-1 for x in input().split()]
Dh,Dw=[int(x)-1 for x in input().split()]
maze=[input() for i in range(H)]
 
dirs=[-2,-1,0,1,2] 


dist=[[float('inf')]*W for _ in range(H)] 
dist[Ch][Cw]=0
dq=deque()
dq.append((0,Ch,Cw)) 
ok=False

while dq:
    k,i,j=dq.popleft()
    if k>dist[i][j]:
        continue
    if i==Dh and j==Dw:
        ok=True
        break
    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 maze[ni][nj]=='
                continue
            if k<dist[ni][nj]: 
                if abs(di)+abs(dj)==1: 
                    nk=k
                    dist[ni][nj]=nk
                    dq.appendleft((nk,ni,nj))
                else: 
                    nk=k+1
                    dist[ni][nj]=nk
                    dq.append((nk,ni,nj))   
if ok:
    ans=dist[Dh][Dw]
else:
    ans=-1
print(ans)

Solution (Python):


import sys
import itertools
from collections import deque

h, w = map(int, sys.stdin.readline().split())
cy, cx = map(lambda x: int(x)-1, sys.stdin.readline().split())
gy, gx = map(lambda x: int(x)-1, sys.stdin.readline().split())
graph = [list(sys.stdin.readline().rstrip()) for _ in range(h)]

distance = [[10**17 for _ in range(w)] for _ in range(h)]
walk = ((1,0), (0,1), (-1, 0), (0, -1))
warp = list(itertools.product(range(-2, 3), repeat=2))

que = deque()
que.append((cy, cx))
distance[cy][cx] = 0

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

    
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if (nx < 0) or (nx > w-1) or (ny < 0) or (ny > h-1): continue
        if (graph[ny][nx] == '.') and (distance[ny][nx] > distance[y][x]):
            distance[ny][nx] = distance[y][x]
            que.appendleft((ny, nx))

    
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy
        if (nx < 0) or (nx > w-1) or (ny < 0) or (ny > h-1): continue
        if (graph[ny][nx] == '.') and (distance[ny][nx] > distance[y][x]+1):
            distance[ny][nx] = distance[y][x]+1
            que.append((ny, nx))

print(distance[gy][gx] if distance[gy][gx] != 10**17 else -1)

Solution (Python):
from collections import deque

def make_wall(maze,h,w):
    maze=deque(maze)
    for i in range(h):
        maze[i]="
    maze.appendleft("
    maze.appendleft("
    maze.append("
    maze.append("
    return list(maze)

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    cost[sy][sx]=0
    walk = [(1, 0), (-1, 0), (0, 1), (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]
    
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return cost[y][x]
        
        
        for i,j in walk:
            ny, nx = y+i, x+j
            if maze[ny][nx] == "." and cost[ny][nx]>cost[y][x]:
                cost[ny][nx]=cost[y][x]
                queue.appendleft([ny,nx])
            
        
        for i, j in warp:
            ny, nx = y+i, x+j
            if cost[ny][nx] > cost[y][x]+1 and maze[ny][nx]==".":
                cost[ny][nx]=cost[y][x]+1
                queue.append([ny,nx])
            
    return -1 

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

maze=[input() for _ in range(h)]

maze=make_wall(maze,h,w)
h+=4
w+=4
sy+=2
sx+=2
gy+=2
gx+=2

INF = 10**12
cost = [[INF]*w for _ in range(h)]

ans=bfs(maze, cost, sy-1, sx-1, gy-1, gx-1)
if ans==INF:
    ans=-1
print(ans)

Solution (Python):
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[0]*h
for i in range(h):
  st=str(input())
  st=list(st)
  s[i]=st
  
from collections import deque
temp=[[999999]*w for i in range(h)]
temp[ch-1][cw-1]=0
queue0 = deque([[ch-1, cw-1, 0]])
queue1 = deque()
while queue0:  
  x,y,c=queue0.popleft()
  queue1.append((x,y,c))
  for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
    xtemp,ytemp=x+i,y+j
    if xtemp<0 or h<=xtemp or ytemp<0 or w<=ytemp or s[xtemp][ytemp]!=".":
      continue
    if temp[xtemp][ytemp]<=c:
      continue
    temp[xtemp][ytemp]=c
    queue0.append([xtemp,ytemp,temp[xtemp][ytemp]])
    
  if len(queue0)==0:      
    while queue1:
      x,y,c=queue1.popleft()
      for i,j in [[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]]:
        xtemp,ytemp=x+i,y+j
        if xtemp<0 or h<=xtemp or ytemp<0 or w<=ytemp or s[xtemp][ytemp]!=".":
          continue
        if temp[xtemp][ytemp]<=c+1:
          continue
        temp[xtemp][ytemp]=c+1
        queue0.append([xtemp,ytemp,temp[xtemp][ytemp]])
        
if temp[dh-1][dw-1]==999999:
  print(-1)
else:
  print(temp[dh-1][dw-1])