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, math
import io, os



from collections import defaultdict as dd, deque, Counter

def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal


INF = float('inf')
mod = int(1e9)+7


h,w=mdata()
ch,cw=mdata()
dh,dw=mdata()
ch,cw,dh,dw=ch-1,cw-1,dh-1,dw-1
S=[data() for i in range(h)]
steps=[(0,1),(1,0),(-1,0),(0,-1)]
dist=[[INF]*w for i in range(h)]
dist[ch][cw]=0

queue = deque()
queue.append((ch, cw))
while queue:
    u, v = queue.popleft()
    d=dist[u][v]
    for i in range(-2, 3):
        for j in range(-2, 3):
            if 0 <= u + i < h and 0 <= v + j < w and S[u + i][v + j] == '.':
                if (i,j) in steps:
                    if d < dist[u+i][v+j]:
                        dist[u+i][v+j] = d
                        queue.appendleft((u+i,v+j))
                else:
                    if 1 + d < dist[u + i][v + j]:
                        dist[u + i][v + j] = 1 + d
                        queue.append((u + i, v + j))


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

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)+1 for x in input().strip().split()]
    Dh, Dw = [int(x)+1 for x in input().strip().split()]
    M = [0 for _ in range(H+4)]
    M[0] = ['
    M[1] = ['
    M[-2] = ['
    M[-1] = ['
    for h in range(2, H+2):
        M[h] = ['
        
    ans = 0
    q = set([(Ch, Cw)])
    M[Ch][Cw] = '
    dhdw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while True:
        newq = set()
        while q:
            q_ = set()
            for h, w in q:
                
                if h == Dh and w == Dw:
                    print(ans)
                    return True
                newq.add((h, w))
                for dh, dw in dhdw:
                    if M[h+dh][w+dw] == '
                        continue
                    q_.add((h+dh, w+dw))
                    M[h+dh][w+dw] = '
            q = q_

        if newq:
            for h, w in newq:
                for dh in range(-2, 3):
                    for dw in range(-2, 3):
                        if M[h+dh][w+dw] == '.':
                            q.add((h+dh, w+dw))
                            M[h+dh][w+dw] = '
        
        
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
i4 = np.int32
i8 = np.int64

INF = 1000000000


def solve(s, ch, cw):
    H = s.shape[0]
    W = s.shape[1] - 1
    ah = H + 4
    aw = W + 4

    a = np.full((ah, aw), -1, i4)
    for i in range(H):
        for j in range(W):
            if s[i, j] == 46:
                a[i + 2, j + 2] = INF

    sh1 = np.empty(1000000, i4)
    sw1 = np.empty(1000000, i4)
    p1 = 0
    sh2 = np.empty(1000000, i4)
    sw2 = np.empty(1000000, i4)
    p2 = 0

    dis = 0
    a[ch + 1, cw + 1] = dis
    sh1[p1] = ch + 1
    sw1[p1] = cw + 1
    p1 += 1

    while True:
        while p1 > 0:
            p1 -= 1
            h = sh1[p1]
            w = sw1[p1]
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if ((i == 1 or i == -1) and j == 0) or (i == 0 and (j == 1 or j == -1)):
                        if a[h + i, w + j] > dis:
                            a[h + i, w + j] = dis
                            sh1[p1] = h + i
                            sw1[p1] = w + j
                            p1 += 1
                    else:
                        if a[h + i, w + j] > dis + 1:
                            a[h + i, w + j] = dis + 1
                            sh2[p2] = h + i
                            sw2[p2] = w + j
                            p2 += 1

        dis += 1
        for i in range(p2):
            if a[sh2[i], sw2[i]] == dis:
                sh1[p1] = sh2[i]
                sw1[p1] = sw2[i]
                p1 += 1
        p2 = 0

        if p1 == 0:
            break

    return a


def main(in_file):
    stdin = open(in_file)
    H, W = [int(x) for x in stdin.readline().split()]
    ch, cw = [int(x) for x in stdin.readline().split()]
    dh, dw = [int(x) for x in stdin.readline().split()]
    s = np.frombuffer(np.array(stdin.read()), i4).reshape((H, W + 1))
    a = solve(s, ch, cw)
    ans = a[dh + 1, dw + 1]
    if ans == INF:
        print(-1)
    else:
        print(ans)


def cc_export():
    from numba.pycc import CC
    from numba import int32, int64
    cc = CC('my_module')
    cc.export('solve', (int32[:,:], int64, int64))(solve)
    cc.compile()


if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import solve
    main('/dev/stdin')

Solution (Python):
from collections import deque


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

    from builtins import max, min, range

    INF = 10 ** 6

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

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

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

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

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

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


main()

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=[input() for _ in range(h)] 
vi=[ [-1 for _ in range(w)] for _ in range(h)]
st=deque()
st2=deque()
st.append([ch-1,cw-1])
vi[ch-1][cw-1]=1
c=0

d=[[0,1],[-1,0],[1,0],[0,-1]]
d2=[[-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]]

while st or st2:
  while st:
    s2=0
    h1,w1=st.popleft()
    if dh-1==h1 and dw-1 ==w1:
      print(c)
      exit()
    for m in d:
      x=w1+m[1]
      y=h1+m[0]
      if 0<=y<h and 0<=x<w:
        if s[y][x]=="." and vi[y][x]==-1:
          st.append([y,x])
        elif s[y][x]=="
        vi[y][x]=1
    if s2==1: st2.append([h1,w1])

  while st2:
    h1,w1=st2.popleft()
    for m in d2:
      x=w1+m[1]
      y=h1+m[0]
      if 0<=y<h and 0<=x<w and vi[y][x]==-1 and s[y][x]==".":
        vi[y][x]=1
        st.append([y,x])
  c+=1
print(-1)

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import deque
from itertools import product
def resolve():
    m, n = map(int, input().split())
    si, sj = map(lambda x : int(x) - 1, input().split())
    ti, tj = map(lambda x : int(x) - 1, input().split())
    grid = [input() for _ in range(m)]

    queue = deque([(si, sj, 0)])
    dist = [[INF] * n for _ in range(m)]
    dist[si][sj] = 0
    while queue:
        i, j, d = queue.popleft()
        if d > dist[i][j]:
            continue
        for di, dj in product(range(-2, 3), repeat = 2):
            if di == dj == 0:
                continue
            ni, nj = i + di, j + dj
            if not (0 <= ni < m and 0 <= nj < n):
                continue
            if grid[ni][nj] == '
                continue
            dd = int(abs(di) + abs(dj) > 1)
            nd = dist[i][j] + dd
            if nd < dist[ni][nj]:
                dist[ni][nj] = nd
                if dd == 0:
                    queue.appendleft((ni, nj, nd))
                else:
                    queue.append((ni, nj, nd))


    ans = dist[ti][tj]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Solution (Python):

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


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

    def __init__(
        self,
        height: int,
        width: int,
        grid: List[str],
        road: str = ".",
        wall: str = "
    ) -> None:
        
        self.height = height + 4
        self.width = width + 4
        self.road = road
        self.wall = wall
        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[str]) -> str:
        flat_grid = self.wall * self.width * 2
        for row in grid:
            flat_grid += self.wall * 2 + row + 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
        move_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),
        }

        unsearched = 1 << 30
        dist = [unsearched] * (self.height * self.width)
        dist[start] = 0
        queue = deque([start])
        while queue:
            x = queue.popleft()
            cur_dist = dist[x]
            if x == goal:
                break

            for move, warp in move_to_warp.items():
                nx = x + move
                if self.grid[nx] == self.road:
                    if dist[nx] > cur_dist:
                        dist[nx] = cur_dist
                        queue.appendleft(nx)
                    continue

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

        return dist[goal] if dist[goal] != 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():
    H, W, CH, CW, DH, DW, *S = open(0).read().split()
    maze = WarpableMaze(int(H), int(W), S)
    start, goal = (int(CH) - 1, int(CW) - 1), (int(DH) - 1, int(DW) - 1)
    print(maze.bfs(start, goal))
    


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import sys,heapq
    input = sys.stdin.buffer.readline

    h,w = map(int,input().split())
    cx,cy = map(int,input().split())
    dx,dy = map(int,input().split())
    cx -= 1
    cy -= 1
    dx -= 1
    dy -= 1

    start = cx*w + cy
    goal = dx*w + dy


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

    dg = 10**7


    edge = [[] for _ in range(h*w)]
    for xy in range(h*w):
        x,y = divmod(xy,w)
        if s[x][y] == 35:
            continue
        for i in range(-2,3):
            for j in range(-2,3):
                if i == 0 and j == 0:
                    continue
                if 0 <= x+i < h and 0 <= y+j < w and s[x+i][y+j] == 46:
                    
                    if (i == 0 and abs(j) == 1) or (j == 0 and abs(i) == 1):
                        edge[xy].append( (x+i)*w + y+j )
                    else:
                        edge[xy].append(dg + (x+i)*w + y+j )

    d = [10**6]*(h*w)
    d[start] = 0

    tank = []

    for e in edge[start]:
        heapq.heappush(tank,e)


    while tank:
        now = heapq.heappop(tank)
        cost,xy = divmod(now,dg)
        if d[xy] != 10**6:
            continue
        d[xy] = cost
        if xy == goal:
            break
        for nxt in edge[xy]:
            if nxt >= dg:
                if d[nxt-dg] == 10**6:
                    heapq.heappush(tank,(cost+1)*dg + nxt-dg)
            else:
                if d[nxt] == 10**6:
                    heapq.heappush(tank,cost*dg + nxt)

    if d[goal] == 10**6:
        print(-1)
    else:
        print(d[goal])

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
from numba import njit, int32, int64
i4 = np.int32
i8 = np.int64

INF = 1000000000


@njit((int32[:,:], int64, int64), cache=True)
def solve(s, ch, cw):
    H = s.shape[0]
    W = s.shape[1] - 1
    ah = H + 4
    aw = W + 4

    a = np.full((ah, aw), -1, i4)
    for i in range(H):
        for j in range(W):
            if s[i, j] == 46:
                a[i + 2, j + 2] = INF

    sh1 = np.empty(1000000, i4)
    sw1 = np.empty(1000000, i4)
    p1 = 0
    sh2 = np.empty(1000000, i4)
    sw2 = np.empty(1000000, i4)
    p2 = 0

    dis = 0
    a[ch + 1, cw + 1] = dis
    sh1[p1] = ch + 1
    sw1[p1] = cw + 1
    p1 += 1

    while True:
        while p1 > 0:
            p1 -= 1
            h = sh1[p1]
            w = sw1[p1]
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if ((i == 1 or i == -1) and j == 0) or (i == 0 and (j == 1 or j == -1)):
                        if a[h + i, w + j] > dis:
                            a[h + i, w + j] = dis
                            sh1[p1] = h + i
                            sw1[p1] = w + j
                            p1 += 1
                    else:
                        if a[h + i, w + j] > dis + 1:
                            a[h + i, w + j] = dis + 1
                            sh2[p2] = h + i
                            sw2[p2] = w + j
                            p2 += 1

        dis += 1
        for i in range(p2):
            if a[sh2[i], sw2[i]] == dis:
                sh1[p1] = sh2[i]
                sw1[p1] = sw2[i]
                p1 += 1
        p2 = 0

        if p1 == 0:
            break

    return a


def main(in_file):
    stdin = open(in_file)
    H, W = [int(x) for x in stdin.readline().split()]
    ch, cw = [int(x) for x in stdin.readline().split()]
    dh, dw = [int(x) for x in stdin.readline().split()]
    s = np.frombuffer(np.array(stdin.read()), i4).reshape((H, W + 1))
    a = solve(s, ch, cw)
    ans = a[dh + 1, dw + 1]
    if ans == INF:
        print(-1)
    else:
        print(ans)


main('/dev/stdin')

Solution (Python):
import sys,heapq
input = sys.stdin.buffer.readline

h,w = map(int,input().split())
cx,cy = map(int,input().split())
dx,dy = map(int,input().split())
cx -= 1
cy -= 1
dx -= 1
dy -= 1

start = cx*w + cy
goal = dx*w + dy


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

dg = 10**7


edge = [[] for _ in range(h*w)]
for xy in range(h*w):
    x,y = divmod(xy,w)
    if s[x][y] == 35:
        continue
    for i in range(-2,3):
        for j in range(-2,3):
            if i == 0 and j == 0:
                continue
            if 0 <= x+i < h and 0 <= y+j < w and s[x+i][y+j] == 46:
                if (i == 0 and abs(j) == 1) or (j == 0 and abs(i) == 1):
                    edge[xy].append( (x+i)*w + y+j )
                else:
                    edge[xy].append(dg + (x+i)*w + y+j )

d = [10**6]*(h*w)
d[start] = 0

tank = []

for e in edge[start]:
    heapq.heappush(tank,e)


while tank:
    now = heapq.heappop(tank)
    cost,xy = divmod(now,dg)
    if d[xy] != 10**6:
        continue
    d[xy] = cost
    if xy == goal:
        break
    for nxt in edge[xy]:
        if nxt >= dg:
            if d[nxt-dg] == 10**6:
                heapq.heappush(tank,(cost+1)*dg + nxt-dg)
        else:
            if d[nxt] == 10**6:
                heapq.heappush(tank,cost*dg + nxt)

if d[goal] == 10**6:
    print(-1)
else:
    print(d[goal])

Solution (Python):
def main():
    import sys
    input=sys.stdin.readline
    
    import heapq
    def dijkstra_heap(st):
        infi=10**18
        
        d = [infi] * h*w
        d[st] = 0
        edgelist = [(0,st)]
        while edgelist:
            dist,idx = heapq.heappop(edgelist)
            x=idx//w
            y=idx%w
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=x+dx
                    ny=y+dy
                    if not (0<=nx<h and 0<=ny<w):
                        continue
                    if dx==0 and dy==0:
                        continue
                    if s[nx][ny]=="
                        continue
                    idx1=nx*w+ny
                    if abs(dx)+abs(dy)==1:
                        if d[idx1]>dist:
                            d[idx1]=d[idx]
                            heapq.heappush(edgelist,(d[idx1],idx1))
                    else:
                        if d[idx1]>dist+1:
                            d[idx1]=dist+1
                            heapq.heappush(edgelist,(d[idx1],idx1))
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    st=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(st)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()

Solution (Python):
import numpy as np
from numba import njit
i4 = np.int32
i8 = np.int64

INF = 1000000000


@njit
def solve(s, ch, cw):
    H = s.shape[0]
    W = s.shape[1] - 1
    ah = H + 4
    aw = W + 4

    a = np.full((ah, aw), -1, i4)
    for i in range(H):
        for j in range(W):
            if s[i, j] == 46:
                a[i + 2, j + 2] = INF

    sh1 = np.empty(1000000, i4)
    sw1 = np.empty(1000000, i4)
    p1 = 0
    sh2 = np.empty(1000000, i4)
    sw2 = np.empty(1000000, i4)
    p2 = 0

    def push2(h2, w2, dis2):
        nonlocal p2, sh2, sw2

    dis = 0
    a[ch + 1, cw + 1] = dis
    sh1[p1] = ch + 1
    sw1[p1] = cw + 1
    p1 += 1

    while True:
        while p1 > 0:
            p1 -= 1
            h = sh1[p1]
            w = sw1[p1]
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if ((i == 1 or i == -1) and j == 0) or (i == 0 and (j == 1 or j == -1)):
                        if a[h + i, w + j] > dis:
                            a[h + i, w + j] = dis
                            sh1[p1] = h + i
                            sw1[p1] = w + j
                            p1 += 1
                    else:
                        if a[h + i, w + j] > dis + 1:
                            push2(h + i, w + j, dis + 1)
                            a[h + i, w + j] = dis + 1
                            sh2[p2] = h + i
                            sw2[p2] = w + j
                            p2 += 1

        dis += 1
        for i in range(p2):
            if a[sh2[i], sw2[i]] == dis:
                sh1[p1] = sh2[i]
                sw1[p1] = sw2[i]
                p1 += 1
        p2 = 0

        if p1 == 0:
            break

    return a


def main(in_file):
    stdin = open(in_file)
    H, W = [int(x) for x in stdin.readline().split()]
    ch, cw = [int(x) for x in stdin.readline().split()]
    dh, dw = [int(x) for x in stdin.readline().split()]
    s = np.frombuffer(np.array(stdin.read()), i4).reshape((H, W + 1))
    a = solve(s, ch, cw)
    ans = a[dh + 1, dw + 1]
    if ans == INF:
        print(-1)
    else:
        print(ans)


main('/dev/stdin')

Solution (Python):
H, W = list(map(int, input().split()))
Ch, Cw = list(map(lambda x:int(x)+1, input().split()))
Dh, Dw = list(map(lambda x:int(x)+1, input().split()))
S = []

S.append(list('
S.append(list('
for i in range(H):
    S.append(list('
S.append(list('
S.append(list('

from collections import deque

q1 = deque()
q2 = deque()
inf = 10**10



T = []
for w in S:
    T_W = [-1 if s=='
    T.append(T_W)


move1 = [(1,0),(0,1),(-1,0),(0,-1)]
move2 = [(i-2,j-2) for i in range(5) for j in range(5)]
move2.remove((0,0))
for t in move1:
    move2.remove(t)
d = 0
h, w = Ch, Cw
T[Ch][Cw] = d
q1.append((h,w))
q2.append((h,w))

ans = -1

while len(q2)>0 or len(q1)>0:
    while len(q1)>0:
        v = q1.popleft()
        for t in [(1,0),(0,1),(-1,0),(0,-1)]:
            h, w = v[0]+t[0], v[1]+t[1]
            if T[h][w] > d:
                if (h,w) == (Dh,Dw):
                    ans = d
                T[h][w] = d
                q1.append((h,w))
                q2.append((h,w))

    d += 1
    while len(q2)>0:
        v = q2.popleft()
        for t in move2:
            h, w = v[0]+t[0], v[1]+t[1]
            if T[h][w] > d:
                if (h,w) == (Dh,Dw):
                    ans = d
                T[h][w] = d
                q1.append((h,w))
    q2.extend(q1)



print(ans)

Solution (Python):

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


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

    def __init__(
        self,
        height: int,
        width: int,
        start: Tuple[int, int],
        goal: Tuple[int, int],
        grid: List[str],
        road: str = ".",
        wall: str = "
    ) -> None:
        
        self.height = height + 4
        self.width = width + 4
        self.start = self._flatten_coordinate(*start)
        self.goal = self._flatten_coordinate(*goal)
        self.road = road
        self.wall = wall
        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[str]) -> str:
        flat_grid = self.wall * self.width * 2
        for row in grid:
            flat_grid += self.wall * 2 + row + self.wall * 2
        flat_grid += self.wall * self.width * 2
        return flat_grid

    def bfs(self) -> int:
        w = self.width
        move_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)),
        )

        unsearched = 1 << 30
        dist = [unsearched] * (self.height * self.width)
        dist[self.start] = 0
        queue = deque([self.start])
        while queue:
            x = queue.popleft()
            cur_dist = dist[x]
            if x == self.goal:
                break

            for move, warp in move_to_warp:
                nx = x + move
                if self.grid[nx] == self.road:
                    if dist[nx] > cur_dist:
                        dist[nx] = cur_dist
                        queue.appendleft(nx)
                else:
                    for dx in warp:
                        nx = x + dx
                        if self.grid[nx] == self.wall:
                            continue
                        if dist[nx] > cur_dist + 1:
                            dist[nx] = cur_dist + 1
                            queue.append(nx)

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

    def debug(self):
        print(f"<DEBUG>\nstart={self.start}, goal={self.goal}", file=sys.stderr)
        for row in zip(*[iter(self.grid)] * self.width):
            print(*row, file=sys.stderr)


def main():
    H, W, CH, CW, DH, DW, *S = open(0).read().split()
    start, goal = (int(CH) - 1, int(CW) - 1), (int(DH) - 1, int(DW) - 1)
    maze = WarpableMaze(int(H), int(W), start, goal, S)
    
    print(maze.bfs())


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque
def resolve():
    drc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for j in range(-2, 3) for i in range(-2, 3) if (i, j) not in drc + [(0, 0)]]
    
    H, W = map(int, input().split())
    sy, sx = map(lambda x: int(x) - 1, input().split())
    gy, gx = map(lambda x: int(x) - 1, input().split())
    
    G = [input() for _ in range(H)]

    dist = [[-1] * W for _ in range(H)]
    q = deque()
    q.append((sy, sx))
    dist[sy][sx] = 0

    while True:
        visited = []
        while q:
            sy, sx = q.popleft()
            visited.append((sy, sx))
            for dy, dx in drc:
                ny = dy + sy
                nx = dx + sx
                if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and dist[ny][nx] == -1:
                    dist[ny][nx] = dist[sy][sx]
                    q.appendleft((ny, nx))

        for sy, sx in visited:
            for dy, dx in warp:
                ny = dy + sy
                nx = dx + sx
                if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and dist[ny][nx] == -1:
                    dist[ny][nx] = dist[sy][sx] + 1
                    q.append((ny, nx))

        if not q or dist[gy][gx] != -1:
            print(dist[gy][gx])
            return


if __name__ == "__main__":
    resolve()

Solution (Python):

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


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

    def __init__(
        self,
        height: int,
        width: int,
        start: Tuple[int, int],
        goal: Tuple[int, int],
        grid: List[str],
        road: str = ".",
        wall: str = "
    ) -> None:
        
        self.height = height + 4
        self.width = width + 4
        self.start = self._flatten_coordinate(*start)
        self.goal = self._flatten_coordinate(*goal)
        self.road = road
        self.wall = wall
        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[str]) -> str:
        flat_grid = self.wall * self.width * 2
        for row in grid:
            flat_grid += self.wall * 2 + row + self.wall * 2
        flat_grid += self.wall * self.width * 2
        return flat_grid

    def bfs(self) -> int:
        w = self.width
        move_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),
        }

        unsearched = 1 << 30
        dist = [unsearched] * (self.height * self.width)
        dist[self.start] = 0
        queue = deque([self.start])
        while queue:
            x = queue.popleft()
            cur_dist = dist[x]
            if x == self.goal:
                break

            for move, warp in move_to_warp.items():
                nx = x + move
                if self.grid[nx] == self.road:
                    if dist[nx] > cur_dist:
                        dist[nx] = cur_dist
                        queue.appendleft(nx)
                else:
                    for dx in warp:
                        nx = x + dx
                        if self.grid[nx] == self.wall:
                            continue
                        if dist[nx] > cur_dist + 1:
                            dist[nx] = cur_dist + 1
                            queue.append(nx)

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

    def debug(self):
        print(f"<DEBUG>\nstart={self.start}, goal={self.goal}", file=sys.stderr)
        for row in zip(*[iter(self.grid)] * self.width):
            print(*row, file=sys.stderr)


def main():
    H, W, CH, CW, DH, DW, *S = open(0).read().split()
    start, goal = (int(CH) - 1, int(CW) - 1), (int(DH) - 1, int(DW) - 1)
    maze = WarpableMaze(int(H), int(W), start, goal, S)
    
    print(maze.bfs())


if __name__ == "__main__":
    main()

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)