Problem:
 Score : 400 points    Problem Statement A maze is composed of a grid of H \times W squares - H vertical, W horizontal.  The square at the i -th row from the top and the j -th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is . .  There is a magician in (C_h,C_w) . He can do the following two kinds of moves:   Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.  Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.   In either case, he cannot go out of the maze.  At least how many times does he need to use the magic to reach (D_h, D_w) ?      Constraints  1 \leq H,W \leq 10^3  1 \leq C_h,D_h \leq H  1 \leq C_w,D_w \leq W  S_{ij} is # or . .  S_{C_h C_w} and S_{D_h D_w} are . .  (C_h,C_w) \neq (D_h,D_w)         Input Input is given from Standard Input in the following format:  H  W  C_h  C_w  D_h  D_w  S_{11}\ldots S_{1W}  \vdots  S_{H1}\ldots S_{HW}       Output Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w) , print -1 instead.        Sample Input 1 4 4
1 1
4 4
..#.
..#.
.#..
.#..      Sample Output 1 1  For example, by walking to (2,2) and then using the magic to travel to (4,4) , just one use of magic is enough.  Note that he cannot walk diagonally.       Sample Input 2 4 4
1 4
4 1
.##.
####
####
.##.      Sample Output 2 -1  He cannot move from there.       Sample Input 3 4 4
2 2
3 3
....
....
....
....      Sample Output 3 0  No use of magic is needed.       Sample Input 4 4 5
1 2
2 5
#.###
####.
#..##
#..##      Sample Output 4 2

Solution (Python):
import sys
import copy
from collections import deque

sys.setrecursionlimit(10**6)
input = sys.stdin.readline


digtmp = [(0, 1), (1, 0), (0, -1), (-1, 0)]
area = [
    (-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
    (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),
    (0, -2), (0, -1), (0, 1), (0, 2),
    (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),
    (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)
]

def warp(a:int, b:int, cnt:int):
    ans = []
    for i, j in area:
        x, y = a+i, b+j
        if 0 <= x < H and 0 <= y < W:
            if field[x][y] == '.' and check[x][y] == -1:
                check[x][y] = cnt
                ans.append((x, y))
    return ans


def main():
    global field, check, H, W
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    field = []
    check = [[-1] * W for _ in range(H)] 
    for h in range(H):
        tmp = list(input()[:-1])
        field.append(tmp)
    
    
    cnt = 0
    que = deque([(Ch-1, Cw-1)])
    for i in range(H*W):
        
        magic = []
        for _ in range(H*W):
            if len(que) == 0:
                break
            a, b = que.popleft()
            magic.append((a, b))
            for dx, dy in digtmp:
                x = a + dx
                y = b + dy
                if not (0 <= x < H and 0 <= y < W):
                    continue
                if check[x][y] != -1 or field[x][y] == '
                    continue
                check[x][y] = cnt
                que.append((x, y))

        
        quetmp = []
        cnt += 1
        for _ in range(H*W):
            a, b = magic.pop()
            tmp = warp(a, b, cnt)
            quetmp += tmp 
            if len(magic) == 0:
                break
        que = deque(quetmp)
        
        if check[Dh-1][Dw-1] != -1:
            print(check[Dh-1][Dw-1])
            return
        if len(que) == 0:
            print(check[Dh-1][Dw-1])
            return


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque


def bfs(sy, sx):
    t = ((-1,0),(0,-1),(1,0),(0,1))
    dist = [[inf]*w for i in range(h)]
    dist[sy][sx] = 0
    q = deque([(sy,sx)])
    while(q):
        y,x = q.popleft()
        d = dist[y][x]
        for i,j in t:
            ny,nx = y+i,x+j
            if (0 <= nx < w and 0 <= ny < h):
                if dist[ny][nx] <= d or s[ny][nx] == "
                    continue
                q.appendleft((y+i,x+j))
                dist[ny][nx] = d
        for i in range(-2,3):
            for j in range(-2,3):
                ny,nx = y+i,x+j
                if (0 <= nx < w and 0 <= ny < h):
                    if dist[ny][nx] <= d+1 or s[ny][nx] == "
                        continue
                    q.append((ny,nx))
                    dist[ny][nx] = d+1
    return dist

inf = 10**9
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [input() for i in range(h)]
ch, cw = ch - 1, cw - 1
dh, dw = dh - 1, dw - 1
dist = bfs(ch,cw)
ans = dist[dh][dw]
if ans == inf:
    ans = -1
print(ans)

Solution (Python):
from collections import deque

def main():
    h, w = map(int, input().split())
    start_h, start_w = map(lambda x: int(x)+1, input().split())
    goal_h, goal_w = map(lambda x: int(x)+1, input().split())

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

    ans = [[-1]*(w+4) for _ in range(h+4)]
    for i in range(h+4):
        for j in range(w+4):
            if s[i][j] == "
                ans[i][j] = -2
    ans[start_h][start_w] = 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, 0), (-1, 1), (-1, 2),(0, -2), (0, -1), (0, 0), (0, 1), (0, 2),(1, -2), (1, -1), (1, 0), (1, 1), (1, 2),(2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

    yet = deque([(start_h, start_w)])
    done = deque()

    while yet:
        x1, y1 = yet.popleft()
        done.append((x1, y1))
        for (p, q) in move1:
            v1, v2 = x1+p, y1+q
            if ans[v1][v2] == -1: 
                yet.append((v1, v2))
                ans[v1][v2] = ans[x1][y1]

        if len(yet) == 0:
            while done:
                x2, y2 = done.popleft()
                for (p, q) in move2:
                    i, j = x2+p, y2+q
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        yet.append((i, j))

    print(ans[goal_h][goal_w])

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque


input = lambda: sys.stdin.readline().rstrip()


if __name__ == "__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())
    maze = [list(input()) for _ in range(H)]
    INF = 10**8
    mc = [[INF]*W for _ in range(H)]
    mc[ch][cw] = 0
    walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    warp = [(y, x) for x in range(-2, 3) for y in range(-2, 3) if abs(y) + abs(x) > 1]
    que = deque()
    que.append((ch, cw, 0))
    while que:
        y, x, w = que.popleft()
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] > w and maze[ny][nx] == ".":
                mc[ny][nx] = w
                que.appendleft((ny, nx, w))
        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] > w+1 and maze[ny][nx] == ".":
                mc[ny][nx] = w + 1
                que.append((ny, nx, w+1))
    if mc[dh][dw] == INF:
        print(-1)
    else:
        print(mc[dh][dw])

Solution (Python):
import sys
from collections import deque


input = lambda: sys.stdin.readline().rstrip()


if __name__ == "__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())
    maze = [list(input()) for _ in range(H)]
    INF = 10**8
    mc = [[INF]*W for _ in range(H)]
    mc[ch][cw] = 0
    walk_que = deque()
    walk_que.append((ch, cw, 0))
    while walk_que:
        y, x, w = walk_que.popleft()
        for ny, nx in [(y+1, x), (y-1, x), (y, x+1), (y, x-1)]:
            if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] > w and maze[ny][nx] == ".":
                mc[ny][nx] = w
                walk_que.appendleft((ny, nx, w))
        for dy in range(-2, 3):
            ny = y + dy
            for dx in range(-2, 3):
                nx = x + dx
                if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] > w+1 and maze[ny][nx] == ".":
                    mc[ny][nx] = w + 1
                    walk_que.append((ny, nx, w+1))
    if mc[dh][dw] == INF:
        print(-1)
    else:
        print(mc[dh][dw])

Solution (Python):
from collections import deque

H, W = map(int,input().split())
sh, sw = map(int,input().split())
gh, gw = map(int,input().split())
sh, sw, gh, gw = sh-1, sw-1, gh-1, gw-1
S = [input() for _ in range(H)]

INF = 10**9
ans = [[INF] * W for _ in range(H)]
ans[sh][sw] = 0

Q = deque([[sh,sw]])
while Q:
    h, w = Q.popleft()

    for nh, nw in [[h,w+1],[h,w-1],[h+1,w],[h-1,w]]:
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == "." and ans[nh][nw] > ans[h][w]:
            ans[nh][nw] = ans[h][w]
            Q.appendleft([nh, nw])

    for nh in range(h-2,h+3):
        for nw in range(w-2,w+3):
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == "." and ans[nh][nw] > ans[h][w] + 1:
                ans[nh][nw] = ans[h][w] + 1
                Q.append([nh,nw])

if ans[gh][gw] == INF:
    print(-1)
else:
    print(ans[gh][gw])

Solution (Python):
from collections import deque

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(list(input()))

d = [[-1 for i in range(W)] for j in range(H)]

Q = deque([[CH - 1, CW - 1, 0]])

while Q:
    x, y, cnt = Q.popleft()
    if d[x][y] != -1:
        continue
    d[x][y] = cnt

    for tx in range(-2, 3):
        for ty in range(-2, 3):
            nx = x + tx
            ny = y + ty
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if abs(tx) + abs(ty) == 1:
                    Q.appendleft([nx, ny, cnt])
                elif abs(tx) + abs(ty) >= 2:
                    Q.append([nx, ny, cnt + 1])

ans = d[DH - 1][DW - 1]


print(ans)

Solution (Python):
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

Solution (Python):
from collections import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())

c = [[] for i in range(h)]

for i in range(h):
    c[i] = input()
    
d = [[10000000 for i in range(w)] for j in range(h)]
    
d[ch-1][cw-1] = 0
que = deque([[ch-1,cw-1]])

dx = [1,0,-1,0]
dy = [0,1,0,-1]
ddx = [1,1,-1,-1,2,2,2,2,2,1,1,0,0,-1,-1,-2,-2,-2,-2,-2]
ddy = [1,-1,1,-1,2,1,0,-1,-2,2,-2,2,-2,2,-2,2,1,0,-1,-2]
    
while que:
    y,x = que.popleft()
        
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[ny][nx] != '
            if d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.appendleft([ny,nx])
                
    for k in range(20):
        nx = x + ddx[k]
        ny = y + ddy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[ny][nx] != '
            if d[ny][nx] > d[y][x] + 1:
                d[ny][nx] = d[y][x] + 1
                que.append([ny,nx])

                
if d[dh-1][dw-1] == 10000000:
    print(-1)
else:
    print(d[dh-1][dw-1])

Solution (Python):
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()]
maze = []
for _ in range(H):
    a = input()
    maze.append(a)
d = deque([(ch, cw, 0)])
value = [[-1 for _ in range(W)] for _ in range(H)]
while d:
    h, w, v = d.popleft()
    if value[h][w] == -1:
        value[h][w] = v
        for hi in range(-2, 3):
            for wi in range(-2, 3):
                next_h = h + hi
                next_w = w + wi
                if (0 <= next_h < H) & (0 <= next_w < W):                
                    if (maze[next_h][next_w] == '.'):
                        if (abs(hi) + abs(wi) == 1) & (value[next_h][next_w] == -1):
                            d.appendleft((next_h, next_w, v))
                        elif (abs(hi) + abs(wi) > 1) & (value[next_h][next_w] == -1):
                            d.append((next_h, next_w, v + 1))
    else:
        continue
print(value[dh][dw])

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 

h,w=map(int,readline().split())
ch, cw=map(int,readline().split())
dh, dw=map(int,readline().split())
m=list(map(lambda x: list(x.decode()), readlines()))

 
ad = [(-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)]
 
def bfs6():
    '''
    bfs5から少し変更
    あるマス(i,j)から上(i-1,j)下(i+1,j) もしくは 左(i,j-1)右(i,j+1)に歩いて行ける時、
    (i,j)からwarpで行ける範囲は、その上下もしくは左右でカバーされるので、(i,jは考えなくていい)
    これをwarpを考えるときに処理する
    '''
    que1=[]
    que2=[] 
    m[ch][cw]=str(0)
    que1.append((ch,cw))
 
    while que1!=[]:
        l1=len(que1)
        r1=0 
 
        
        while r1<l1:
            i, j=que1[r1]
            r1+=1
            for si, sj in ad:
                if m[i+si][j+sj]=='.': 
                    m[i+si][j+sj]=m[i][j]
                    que1.append((i+si, j+sj))
                    l1+=1
 
        
        for i,j in que1:
            if (m[i][j]==m[i-1][j] and m[i][j]==m[i+1][j]) or (m[i][j]==m[i][j-1] and m[i][j]==m[i][j+1]):
                continue
            for si, sj in warp:
                if m[i+si][j+sj]=='.':
                    m[i+si][j+sj]=str(int(m[i][j])+1)
                    que2.append((i+si, j+sj))
 
        que1=que2
        que2=[]

 
for i in range(h):
    m[i] = ['
    
m = [['
ch+=1; cw+=1; dh+=1; dw+=1
 
bfs6()
 
if m[dh][dw] == '.':
    print(-1)
else:
    print(m[dh][dw])

Solution (Python):
from collections import deque

H, W = map(int, input().split())
si, sj = map(int, input().split())
gi, gj = map(int, input().split())
si, sj, gi, gj = si - 1, sj - 1, gi - 1, gj - 1
C = [input() for i in range(H)]

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

que = deque()
que.append((si, sj))

while que:
    i, j = que.popleft()
    d = dist[i][j]
    if i == gi and j == gj:
        break
    for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
        if not (0 <= ni < H and 0 <= nj < W):
            continue
        if d < dist[ni][nj] and C[ni][nj] == ".":
            dist[ni][nj] = d
            que.appendleft((ni, nj))
    for di in range(-2, 3):
        for dj in range(-2, 3):
            ni, nj = i + di, j + dj
            if not (0 <= ni < H and 0 <= nj < W):
                continue
            if d + 1 < dist[ni][nj] and C[ni][nj] == ".":
                dist[ni][nj] = d + 1
                que.append((ni, nj))

ans = dist[gi][gj]
print(ans if ans != 10 ** 9 else -1)

Solution (Python):
import sys
from collections import deque

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=[[*next(sys.stdin)] for _ in range(H)]

N=-1
for i in range(H):
    for j in range(W):
        if A[i][j]!='.':
            continue
        N+=1
        stk=[(i,j)]
        while stk:
            ii,jj=stk.pop()
            A[ii][jj]=N
            for ni,nj in (ii-1,jj),(ii,jj+1),(ii+1,jj),(ii,jj-1):
                if not (0<=ni<H and 0<=nj<W):
                    continue
                if A[ni][nj]!='.':
                    continue
                stk.append((ni,nj))

s=t=-1
dirs=[-2,-1,0,1,2]
adj=[{*()} for _ in range(N+1)]
for i in range(H):
    for j in range(W):
        u=A[i][j]
        if u=='
            continue
        if i==si and j==sj:
            s=u
        elif i==ti and j==tj:
            t=u
        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
                v=A[ni][nj]
                if v=='
                    continue
                if u!=v:
                    adj[u].add(v)
                    adj[v].add(u)

que=deque()                
que.append(s)
vis={s}
m=-1
ok=False
while que:
    m+=1
    for _ in range(len(que)):
        u=que.popleft()
        if u==t:
            ok=True
            break
        for v in adj[u]:
            if v in vis:
                continue
            vis.add(v)
            que.append(v)
    if ok:
        break

if ok:
    print(m)
else:
    print(-1)

Solution (Python):
from collections import deque

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





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

wx = [-2, -1, 0, 1, 2]
wy = [-2, -1, 0, 1, 2]
dp = [[-1] * W for _ in range(H)]
dp[Ch - 1][Cw - 1] = 0


def bfs(x, y, cost, dp, d):
    while len(d) > 0:
        p = d.popleft()
        dw.append(p)
        for i in range(4):
            if p[0] + dx[i] >= 0 and p[0] + dx[i] < W and p[1] + \
                    dy[i] >= 0 and p[1] + dy[i] < H:
                if S[p[1] + dy[i]][p[0] + dx[i]
                                   ] == '.' and dp[p[1] + dy[i]][p[0] + dx[i]] == -1:
                    d.append([p[0] + dx[i], p[1] + dy[i]])
                    dw.append([p[0] + dx[i], p[1] + dy[i]])
                    dp[p[1] + dy[i]][p[0] + dx[i]] = cost

    return cost, dp


ds = deque()
ds.append([Cw - 1, Ch - 1])
c = 0
while True:
    dw = deque()
    cost, dp = bfs(Cw - 1, Ch - 1, c, dp, ds)
    check = False
    while len(dw) > 0:
        p = dw.popleft()
        for m in range(5):
            for n in range(5):
                if p[0] + wx[m] >= 0 and p[0] + wx[m] < W and p[1] + \
                        wy[n] >= 0 and p[1] + wy[n] < H:
                    if S[p[1] + wy[n]][p[0] + wx[m]
                                       ] == '.' and dp[p[1] + wy[n]][p[0] + wx[m]] == -1:
                        ds.append([p[0] + wx[m], p[1] + wy[n]])
                        dp[p[1] + wy[n]][p[0] + wx[m]] = cost + 1
                        check = True
    if check:
        c += 1
    else:
        break

print(dp[Dh - 1][Dw - 1])

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

start_h = c_h - 1
start_w = c_w - 1
goal_h = d_h - 1
goal_w = d_w - 1

maze = [input() for _ in range(h)]
inf = float("inf")
dist = [[inf] * w for _ in range(h)]



def bfs(x, y):
    dist[x][y] = 0
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft() 
        d = dist[x][y]
        for dx, dy in [(0,1),(1,0),(0,-1),(-1,0)]:
            nx = x + dx
            ny = y + dy 
            if not 0 <= nx < h or not 0 <= ny < w:
                continue
            if maze[nx][ny] == "
                continue
            if dist[nx][ny] <= d:
                continue
            dist[nx][ny] = d           
            q.appendleft((nx, ny))

        for dxx in range(-2, 3):
            for dyy in range(-2, 3):
                 nxx = x + dxx
                 nyy = y + dyy 
                 if not 0 <= nxx < h or not 0 <= nyy < w:
                    continue
                 if maze[nxx][nyy] == "
                    continue
                 if dist[nxx][nyy] <= d+1:
                    continue
                 dist[nxx][nyy] = d+1
                 q.append((nxx, nyy))
                



bfs(start_h, start_w)
if dist[goal_h][goal_w] == inf:
    print("-1")
else:
    print(dist[goal_h][goal_w])

Solution (Python):
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    
    
    
    maze = ['
    maze.append('
    for _ in range(h):
        maze.append('
    maze.append('
    maze.append('
    visited = [[-1] * (w+4) for _ in range(h+4)]
    for i in range(h+4):
        for j in range(w+4):
            if maze[i][j] == '
                visited[i][j] = -2
    
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    visited[ch][cw] = 0
    walk = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    telepo = [[i,j] for i in range(-2, 3) for j in range(-2, 3)]

    q_walk = deque([[ch, cw]])
    q_telepo = deque([])
    while q_walk:
        yw, xw = q_walk.popleft()
        
        q_telepo.append([yw, xw])
        for i, j in walk:
            ny, nx = yw + i, xw + j
            
            
            if visited[ny][nx] == -1:
                
                visited[ny][nx] = visited[yw][xw]
                q_walk.append([ny, nx])
        
        if len(q_walk) == 0:
            while q_telepo:
                yt, xt = q_telepo.popleft()
                for i, j in telepo:
                    my, mx = yt + i, xt + j
                    
                    
                    
                    
                    if visited[my][mx] == -1:
                        visited[my][mx] = visited[yt][xt] + 1
                        q_walk.append([my, mx])
    print(visited[dh][dw])

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

INF = int(1e10)

dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]

def main():
    from builtins import int, map
    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 = [list(input()) for _ in range(H)]

    dist = [[INF] * W for _ in range(H)]
    dist[Ch][Cw] = 0
    queue = deque([(Ch, Cw)])

    while queue:
        (h, w) = queue.popleft()

        for i in range(4):
            dhi, dwi = dh[i], dw[i]
            nh, nw = h + dhi, w + dwi
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                if dist[h][w] < dist[nh][nw]:
                    dist[nh][nw] = dist[h][w]
                    queue.appendleft((nh, nw))
        
        
        for ddh in range(-2, 3):
            for ddw in range(-2, 3):
                if abs(ddh) + abs(ddw) <= 1:
                    continue
                nh, nw = h + ddh, w + ddw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                    if dist[nh][nw] > dist[h][w] + 1:
                        dist[nh][nw] = dist[h][w] + 1
                        queue.append((nh, nw))

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

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
INF = int(1e10)

def main():
    from builtins import int, map
    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 = [input() for _ in range(H)]

    
    dist = [[float("inf")] * W for _ in range(H)]
    queue = deque([(Ch, Cw, 0)])

    while queue:
        (h, w, d) = queue.popleft()

        if dist[h][w] == float("inf") or dist[h][w] > d:
            dist[h][w] = d
            
            
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nh, nw = h + ddh, w + ddw
                    if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                        
                        if abs(ddh) + abs(ddw) <= 1:
                            queue.appendleft((nh, nw, d))
                        
                        else:
                            queue.append((nh, nw, d + 1))

    if dist[Dh][Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh][Dw])

if __name__ == '__main__':
    main()

Solution (Python):
from numba import njit
import numpy as np
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

@njit(cache=True)
def pos(W,h,w):
    return h * W + w



def solve(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) 
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) 
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]



def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "

    ans = solve(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    
    cc.export('pos', '(i8,i8,i8,)')(pos)
    cc.export('solve', '(i8,i8,i8,i8,i8,i8,b1[:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    try:
        from my_module import solve
        from my_module import pos
    except:
        cc_export()
        exit()

    main()

Solution (Python):
def resolve():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    dh, dw = map(int, input().split())
    dh -= 1
    dw -= 1
    maze = []
    for _ in range(h):
        maze.append(list(input()))

    final = [[10**9] * w for _ in range(h)]
    from collections import deque
    nxt = [[ch, cw]]
    nxt = deque(nxt)
    final[ch][cw] = 0

    while nxt:
        nowh, noww = nxt.popleft()
        for i, j in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
            if 0 <= nowh + i < h and 0 <= noww + j < w and maze[nowh + i][noww + j] == ".":
                if final[nowh + i][noww + j] > final[nowh][noww]:
                    final[nowh + i][noww + j] = final[nowh][noww]
                    nxt.appendleft([nowh + i, noww + j])


        for i in range(max(0, nowh - 2), min(h, nowh + 3)):
            for j in range(max(0, noww - 2), min(w, noww + 3)):
                if maze[i][j] == ".":
                    if final[i][j] > final[nowh][noww] + 1:
                        final[i][j] = final[nowh][noww] + 1
                        nxt.append([i, j])
    if final[dh][dw] == 10**9:
        print(-1)
    else:
        print(final[dh][dw])

resolve()

Solution (Python):


from collections import deque

q = 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

ban_list = [[-999 for j in range(w)] for i in range(h)]


for i in range(h):
  
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]


ban_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])


ido_h = [-1, 0, 1, 0]
ido_w = [0, 1, 0, -1]

while q:
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  for i in range(4):
    nh = ph + ido_h[i]
    nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = ban_list[nh][nw]
    if val == "
      continue
    if val == "." or cost < val:
      ban_list[nh][nw] = cost
      q.appendleft([nh, nw])



  
  
  
  
  
  
  
  
  
  
  

  
  
  
  
  
  
  
  
  
  

  
  
  
  
  
  
  
  
  
  

  
  
  
  
  
  
  
  
  
  


  
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])


result = ban_list[dh][dw]
if result == ".":
  result = -1


print(result)

Solution (Python):
from numba import njit
import numpy as np
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

@njit(cache=True)
def pos(W,h,w):
    return h * W + w



def solve(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) 
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) 
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]



def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "

    ans = solve(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    cc.export('pos', '(i8,i8,i8,)')(pos)
    cc.export('solve', '(i8,i8,i8,i8,i8,i8,b1[:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    try:
        from my_module import solve
        from my_module import pos
    except:
        cc_export()
        exit()

    main()