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
INF = -1
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
S = []
for i in range(H):
    S.append(list(input()))
ans = [[INF] * W for _ in range(H)]
dx = (1,0,-1,0)
dy = (0,1,0,-1)
que = deque([(Ch,Cw,0)])
while len(que) != 0:
    p = que.popleft()
    if ans[ p[0] ][ p[1] ] == INF:
        ans[p[0]][p[1]] = p[2]
        if p[0] == Dh and p[1] == Dw:
            break
        for i in range(4):
            h = p[0]+dx[i]
            w = p[1]+dy[i]
            if (0 <= h and H > h) and (0 <= w and W > w) and (S[h][w] != '
                que.appendleft((h,w,p[2]))
        for i in range(-2,3):
            for j in range(-2,3):
                h = p[0]+i
                w = p[1]+j
                if (0 <= h and H > h) and (0 <= w and W > w) and (S[h][w] != '
                    que.append((h,w,p[2]+1))
    

print(ans[Dh][Dw])

Solution (Python):
import collections

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = []
for i in range(h):
    s.append(list(input()))
num = [[float("inf") for i in range(w)] for i in range(h)]
flag = [[False for i in range(w)] for i in range(h)]
num[ch - 1][cw - 1] = 0
queue = collections.deque([[ch, cw]])
d1 = [[-1, 0], [1, 0], [0, -1], [0, 1]]
d2 = [[-1, -1], [-1, 1], [1, -1], [1, 1], [-2, 0], [2, 0], [0, -2], [0, 2]]
d3 = [[-2, -1], [-1, -2], [2, -1], [1, -2], [-2, 1], [-1, 2], [2, 1], [1, 2]]
d4 = [[-2, -2], [-2, 2], [2, -2], [2, 2]]
while queue:
    test = queue.popleft()
    x = test[1]
    y = test[0]
    if flag[y - 1][x - 1] == True:
        continue
    
    
    flag[y - 1][x - 1] = True
    temp = num[y - 1][x - 1]
    for i in d1:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == ".":
            num[y2 - 1][x2 - 1] = min(num[y2 - 1][x2 - 1], temp)
            queue.appendleft([y2, x2])
    for i in d2:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == ".":
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            queue.append([y2, x2])
    for i in d3:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == ".":
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            queue.append([y2, x2])
    for i in d4:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == ".":
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            queue.append([y2, x2])
if num[dh - 1][dw - 1] == float("inf"):
    print(-1)
else:
    print(num[dh - 1][dw - 1])

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


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

from collections import deque

def resolve():
    H, W = iim()
    Ch, Cw = iim()
    Dh, Dw = iim()
    W1 = W+4; H1 = H+4

    ok = "."
    X = "X"
    X2 = "XX"
    XX = X2 * W1

    S = XX + "".join(X2 + input() + X2 for i in range(H)) + XX

    pos1 = W1 * (Ch+1) + (Cw+1)
    pos2 = W1 * (Dh+1) + (Dw+1)

    dp = [0] * (H1*W1)
    dp[pos1] = 1

    dq = deque([(1, pos1)])
    step = (-2*W1 -2,) + (1,)*4 + (W1,)*4 + (-1,)*4 + (-W1,)*3 + (1, 2, 2*W1, -2)

    while dq:
        n, p0 = dq.popleft()

        if p0 == pos2:
            print(n-1)
            return


        x1 = 0
        for i in (1, -1, W1, -W1):
            p1 = p0 + i
            if S[p1] != ok:
                continue

            if dp[p1] == 0 or n < dp[p1]:
                dp[p1] = n
                dq.appendleft((n, p1))


        n1 = n + 1
        p1 = p0
        for i in step:
            p1 += i
            if dp[p1] or S[p1] != ok:
                continue
            dp[p1] = n1
            dq.append((n1, p1))

    print(-1)

if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())

cy -= 1
cx -= 1
gy -= 1
gx -= 1

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

q = deque()
q2 = set()

q.append((cx, cy, 0))

visited = [[float("inf") for _ in range(W)] for _ in range(H)]

visited[cy][cx] = 0
ans = float("inf")

while q:
    while q:
        x, y, c = q.popleft()
        
        if visited[y][x] < c:
            
            continue
        
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nx = x + dx
            ny = y + dy
            if 0 <= nx < W and 0 <= ny < H:
                if grid[ny][nx] == "
                    q2.add((x, y, c))
                else:
                    
                    if visited[ny][nx] <= c:
                        
                        continue
                    
                    visited[ny][nx] = c
                    if nx == gx and ny == gy:
                        continue
                    q.append((nx, ny, c))

    for x, y, c in q2:
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                    continue
                nx = x + dx
                ny = y + dy
                
                if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "
                    
                    
                    if visited[ny][nx] < c + 1:
                        
                        continue
                    
                    visited[ny][nx] = c + 1
                    if nx == gx and ny == gy:
                        continue
                    q.append((nx, ny, c+1))
    q2 = set()


if visited[gy][gx] == float("inf"):
    print(-1)
else:
    print(visited[gy][gx])

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


ud=[(-1,0), (1,0)] 
lr=[(0,-1), (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 bfs5():
    '''
    bfs4から少し変更
    あるマス(i,j)から上(i-1,j)下(i+1,j) もしくは 左(i,j-1)右(i,j+1)に歩いて行ける時、
    (i,j)からwarpで行ける範囲は、その上下もしくは左右でカバーされるので、(i,jは考えなくていい)
    '''
    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]
            cnt_ud=0
            
            for si, sj in ud:
                if m[i+si][j+sj]=='.': 
                    m[i+si][j+sj]=m[i][j]
                    que1.append((i+si, j+sj))
                    cnt_ud+=1
            cnt_lr=0
            
            for si, sj in lr:
                if m[i+si][j+sj]=='.': 
                    m[i+si][j+sj]=m[i][j]
                    que1.append((i+si, j+sj))
                    cnt_lr+=1

            if cnt_ud==2 or cnt_lr==2: 
                que1.pop(r1); l1+=cnt_ud+cnt_lr-1
            else: 
                r1+=1; l1+=cnt_ud+cnt_lr

        
        for i,j in que1:
            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

bfs5() 
if m[dh][dw] == '.':
    print(-1)
else:
    print(m[dh][dw])

Solution (Python):

import sys
from collections import deque
from typing import List, Tuple


class WarpableMaze:
    __slots__ = ["height", "width", "road", "wall", "unsearched", "grid"]

    def __init__(
        self,
        height: int,
        width: int,
        grid: List[bytes],
        road: str = ".",
        wall: str = "
    ) -> None:
        self.height = height + 4
        self.width = width + 4
        self.road = road
        self.wall = wall
        self.unsearched = 1 << 30
        self.grid = self._flatten_grid(grid)

    def _flatten_dxy(self, x: int, y: int) -> int:
        return self.width * x + y

    def _flatten_coordinate(self, h: int, w: int) -> int:
        return self._flatten_dxy(h + 2, w + 2)

    def _flatten_grid(self, grid: List[bytes]) -> str:
        flat_grid = self.wall * (self.width * 2)
        for row in grid:
            flat_grid += self.wall * 2 + row.decode() + self.wall * 2
        flat_grid += self.wall * (self.width * 2)
        return flat_grid

    def bfs(self, start_2d: Tuple[int, int], goal_2d: Tuple[int, int]) -> int:
        start = self._flatten_coordinate(*start_2d)
        goal = self._flatten_coordinate(*goal_2d)

        w = self.width
        walk_to_warp = {
            -w: (-2 * w - 2, -2 * w - 1, -2 * w, -2 * w + 1, -w - 1),
            w: (w + 1, 2 * w - 1, 2 * w, 2 * w + 1, 2 * w + 2),
            -1: (-w - 2, -2, w - 2, w - 1, 2 * w - 2),
            1: (-w + 1, -2 * w + 2, -w + 2, 2, w + 2),
        }

        convert = lambda c: self.unsearched if c == self.road else -1
        dist = list(map(convert, self.grid))
        dist[start] = 0
        queue = deque([start])
        while queue:
            x = queue.popleft()
            cur_dist = dist[x]
            if x == goal:
                break

            for walk, warp in walk_to_warp.items():
                nx = x + walk
                if dist[nx] > cur_dist:
                    dist[nx] = cur_dist
                    queue.appendleft(nx)
                    continue
                if dist[nx] >= 0:
                    continue

                for dx in warp:
                    nx = x + dx
                    if dist[nx] > cur_dist + 1:
                        dist[nx] = cur_dist + 1
                        queue.append(nx)

        return dist[goal] if dist[goal] != self.unsearched else -1

    def debug(self):
        print("<DEBUG>", file=sys.stderr)
        for row in zip(*[iter(self.grid)] * self.width):
            print(*row, file=sys.stderr)


def main():
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline

    H, W = map(int, readline().split())
    CH, CW = map(int, readline().split())
    DH, DW = map(int, readline().split())
    (*S,) = read().split()

    maze = WarpableMaze(H, W, S)
    start, goal = (CH - 1, CW - 1), (DH - 1, DW - 1)
    print(maze.bfs(start, goal))
    


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
def solve():
    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())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    

    start_area_num = int(V[Ch][Cw])
    goal_area_num = int(V[Dh][Dw])

    visited = [False] * vertex

    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                visited[next_area_num] = True
                q.append((next_area_num, warp_cnt+1))
    else:
        print(-1)

if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque
def solve():
    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())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    

    start_area_num = int(V[Ch][Cw])
    goal_area_num = int(V[Dh][Dw])

    visited = [False] * vertex
    visited[start_area_num] = True

    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                visited[next_area_num] = True
                q.append((next_area_num, warp_cnt+1))
    else:
        print(-1)

if __name__ == '__main__':
    solve()

Solution (Python):
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())

cy -= 1
cx -= 1
gy -= 1
gx -= 1

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

q = deque()

q.append((cx, cy, 0))

visited = [[float("inf") for _ in range(W)] for _ in range(H)]

visited[cy][cx] = 0
ans = float("inf")

while q:
    x, y, c = q.popleft()
    
    if visited[y][x] < c:
        
        continue
    
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "
            
            if visited[ny][nx] <= c:
                
                continue
            
            visited[ny][nx] = c
            if nx == gx and ny == gy:
                continue
            q.appendleft((nx, ny, c))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "
                
                
                if visited[ny][nx] < c + 1:
                    
                    continue
                
                visited[ny][nx] = c + 1
                if nx == gx and ny == gy:
                    continue
                q.append((nx, ny, c+1))

if visited[gy][gx] == float("inf"):
    print(-1)
else:
    print(visited[gy][gx])

Solution (Python):
from collections import deque
def solve():
    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())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    

    start_area_num = int(V[Ch][Cw])
    goal_area_num = int(V[Dh][Dw])

    dist = [-1] * vertex
    visited = [False] * vertex
    dist[start_area_num] = 0
    visited[start_area_num] = True

    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(dist[cur_area_num])
            return
        
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                dist[next_area_num] = dist[cur_area_num] + 1
                visited[next_area_num] = True
                q.append((next_area_num, warp_cnt+1))
    else:
        print(-1)

if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque
def solve():
    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())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    

    start_area_num = int(V[Ch][Cw])
    goal_area_num = int(V[Dh][Dw])

    dist = [-1] * vertex
    visited = [False] * vertex
    dist[start_area_num] = 0
    visited[start_area_num] = True

    q = deque()
    q.append(start_area_num)
    while len(q) > 0:
        cur_area_num = q.popleft()
        if cur_area_num == goal_area_num:
            print(dist[cur_area_num])
            return
        
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                dist[next_area_num] = dist[cur_area_num] + 1
                visited[next_area_num] = True
                q.append(next_area_num)
    else:
        print(-1)

if __name__ == '__main__':
    solve()

Solution (Python):
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
maze = [input() for _ in range(h)]
walk = [(-1, 0),  (1, 0), (0, -1), (0, 1)]
teleport = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
            (-1, -2), (-1, -1),          (-1, 1), (-1, 2),
            (0, -2),                              (0, 2),
            (1, -2),  (1, -1),           (1, 1),  (1, 2),
            (2, -2),  (2, -1),  (2, 0),  (2, 1),  (2, 2)]

INF = 10 ** 9
mp = [[INF for _ in range(w)] for _ in range(h)]
mp[ch][cw] = 0
walkable = [(ch, cw)]
while True:
    for y, x in walkable:
        for dy, dx in walk:
            ny, nx = y + dy, x + dx
            if (ny < 0 or h <= ny) or (nx < 0 or w <= nx):
                continue
            if maze[ny][nx] == '
                continue
            if mp[ny][nx] != INF:
                continue
            mp[ny][nx] = mp[y][x]
            walkable.append((ny, nx))

    teleportable = []
    for y, x in walkable:
        for dy, dx in teleport:
            ny, nx = y + dy, x + dx
            if (ny < 0 or h <= ny) or (nx < 0 or w <= nx):
                continue
            if maze[ny][nx] == '
                continue
            if mp[ny][nx] != INF:
                continue
            mp[ny][nx] = mp[y][x] + 1
            teleportable.append((ny, nx))

    if mp[dh][dw] != INF:
        print(mp[dh][dw])
        break
    if teleportable == []:
        print(-1)
        break
    walkable = teleportable

Solution (Python):
import heapq
class Dijkstra:
    INF = 10**18
    threshold = 10**9

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost): self.G[X].append((cost, Y))

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, (0, st))
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)
            cost = p[0]
            node = p[1]
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to[0]
                to_node = to[1]
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, (to_cost, to_node))

h, w = map(int, input().split())
sh, sw = map(int, input().split())
eh, ew = map(int, input().split())

sh -= 1
sw -= 1
eh -= 1
ew -= 1

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

di = Dijkstra(h*w)
for x in range(h):
    for y in range(w):
        if S[x][y] == '
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + i
                Y = y + j
                if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '
                D = abs(i) + abs(j)

                if D == 1: di.insert(x * w + y, X * w + Y, 0)
                if D >= 2: di.insert(x * w + y, X * w + Y, 1)

di.dijkstra(sh * w + sw)
ans = di.dist[eh * w + ew]
if ans == 10**18: print(-1)
else: print(ans)

Solution (Python):

import sys
from collections import deque
from typing import List, Tuple


class WarpableMaze:
    __slots__ = ["height", "width", "unsearched", "dist"]

    def __init__(
        self,
        height: int,
        width: int,
        grid: List[bytes],
        road: str = ".",
    ) -> None:
        self.height = height + 4
        self.width = width + 4
        self.unsearched = 1 << 30
        self.dist = self._convert_grid_to_dist(grid, road)

    def _convert_grid_to_dist(self, grid: List[bytes], road: str) -> List[int]:
        dist = [-1] * self.height * self.width
        i = self.width * 2 + 1
        for row in grid:
            for c in row.decode():
                i += 1
                if c == road:
                    dist[i] = self.unsearched
            i += 4
        return dist

    def _flatten_coordinate(self, x: int, y: int) -> int:
        return self.width * (x + 2) + y + 2

    def bfs(self, start_2d: Tuple[int, int], goal_2d: Tuple[int, int]) -> int:
        start = self._flatten_coordinate(*start_2d)
        goal = self._flatten_coordinate(*goal_2d)

        w = self.width
        walk_to_warp = {
            -w: (-2 * w - 2, -2 * w - 1, -2 * w, -2 * w + 1, -w - 1),
            w: (w + 1, 2 * w - 1, 2 * w, 2 * w + 1, 2 * w + 2),
            -1: (-w - 2, -2, w - 2, w - 1, 2 * w - 2),
            1: (-w + 1, -2 * w + 2, -w + 2, 2, w + 2),
        }

        dist = self.dist[:]
        dist[start] = 0
        queue = deque([start])
        while queue:
            x = queue.popleft()
            cur_dist = dist[x]
            if x == goal:
                break

            for walk, warp in walk_to_warp.items():
                nx = x + walk
                if dist[nx] > cur_dist:
                    dist[nx] = cur_dist
                    queue.appendleft(nx)
                    continue
                if dist[nx] >= 0:
                    continue

                for dx in warp:
                    nx = x + dx
                    if dist[nx] > cur_dist + 1:
                        dist[nx] = cur_dist + 1
                        queue.append(nx)

        return dist[goal] if dist[goal] != self.unsearched else -1


def main():
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline

    H, W = map(int, readline().split())
    CH, CW = map(int, readline().split())
    DH, DW = map(int, readline().split())
    (*S,) = read().split()

    maze = WarpableMaze(H, W, S)
    start, goal = (CH - 1, CW - 1), (DH - 1, DW - 1)
    print(maze.bfs(start, goal))


if __name__ == "__main__":
    main()