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



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Accepted

Solution code:
# D - Wizard in Maze
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:
        # Values of start and goal must be 0-origin.
        self.height = height + 4
        self.width = width + 4
        self.road = road
        self.wall = wall
        self.grid = self._flatten_grid(grid)

    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 _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 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
        flatten = lambda *dxy: tuple(self._flatten_dxy(_dx, _dy) for _dx, _dy in dxy)
        move_to_warp = {
            -w: flatten((-2, -2), (-2, -1), (-2, 0), (-2, 1), (-1, -1)),
            w: flatten((1, 1), (2, -1), (2, 0), (2, 1), (2, 2)),
            -1: flatten((-1, -2), (0, -2), (1, -2), (1, -1), (2, -2)),
            1: flatten((-1, 1), (-2, 2), (-1, 2), (0, 2), (1, 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))
    # maze.debug()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
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
#from fractions import Fraction
#sys.setrecursionlimit(100000)
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)

Submission status: Accepted

Solution code:
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] = ['#'] * (W+4)
    M[1] = ['#'] * (W+4)
    M[-2] = ['#'] * (W+4)
    M[-1] = ['#'] * (W+4)
    for h in range(2, H+2):
        M[h] = ['#'] * 2 + list(input().strip()) + ['#'] * 2
        # print(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:
                # print('({}, {}) = {}'.format(h, w, ans))
                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] = '#'
        # for h in range(H):
        #     print(M[h])
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
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()

Submission status: Accepted

Solution code:
# D - Wizard in Maze
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:
        # Values of start and goal must be 0-origin.
        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))
    # maze.debug()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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('#'*(W+4)))
S.append(list('#'*(W+4)))
for i in range(H):
    S.append(list('#'*2+input()+'#'*2))
S.append(list('#'*(W+4)))
S.append(list('#'*(W+4)))

from collections import deque

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


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

# print(T)
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)

Submission status: Accepted

Solution code:
# D - Wizard in Maze
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:
        # Values of start and goal must be 0-origin.
        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)
    # maze.debug()
    print(maze.bfs())


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

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