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:
# 参考: White_Pie_46
# https://atcoder.jp/contests/abc176/submissions/16168825
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)
    warp_can_reach = tuple(gen_warp_can_reach())
    qu = deque()
    qu.append((init_h, init_w, 0))  # 座標とワープ回数を保持
    reached = set()

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if (h, w) in reached:
            # 同じマスを複数回キューに追加しているかもしれない。
            # 短距離で調査済みなら再調査は不要。
            continue
        reached.add((h, w))

        for h_delta, w_delta in adjacents:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    qu.appendleft((new_h, new_w, warps))

        for h_delta, w_delta in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    qu.append((new_h, new_w, warps + 1))
    return -1


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

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    Ch, Cw = (int(i)-1 for i in input().split())
    Dh, Dw = (int(i)-1 for i in input().split())
    A = [input() for i in range(H)]
    V = [[-1]*W for i in range(H)]  # V[h][w]を頂点iとする
    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 not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if V[next_h][next_w] != -1:
                    continue
                if A[next_h][next_w] == '#':
                    continue
                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] == "#" or V[h][w] != -1:
                continue
            bfs_2d(h, w, vertex)
            vertex += 1

    # グラフを作成、全てのマスで5*5の範囲を走査
    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, 3):
                for dw in range(-2, 3):
                    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]))

    # for h in range(H):
    #     print(V[h])

    # for i in range(vertex):
    #     print(G[i])

    # スタートからゴールまでbfsして最短距離を求める
    s = V[Ch][Cw]
    g = V[Dh][Dw]

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)

    print(dist[g])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import count
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


MOVES = [
    ((1, 0), [(2,-1),(2,0),(2,1),(2,2),(1,1)]),
    ((-1, 0),[(-2,-1),(-2,0),(-2,1),(-2,-2),(-1,-1)]),
    ((0, 1), [(1,2),(0,2),(-1,2),(-2,2),(-1,1)]),
    ((0, -1), [(1,-2),(0,-2),(-1,-2),(2,-2),(1,-1)]),
    ]

CONVERTED_MOVES = None

def solve(dist, start, goal):
    q = [start]
    cnt = 0
    while q:
        nq = []
        while q:
            x = q.pop()
            if x == goal:
                return cnt
            if dist[x] < cnt:
                continue
            for d,l in CONVERTED_MOVES:
                nx = x+d
                if dist[nx] > cnt:
                    dist[nx] = cnt
                    q.append(nx)
                if dist[nx] < 0:
                    for t in l:
                        p = x+t
                        if dist[p] > cnt+1:
                            dist[p] = cnt+1
                            nq.append(p)
        q = nq
        cnt += 1

    return -1




if __name__ == '__main__':
    H,W = map(int,readline().split())
    start = tuple(map(lambda i:int(i)+1,readline().split()))
    goal = tuple(map(lambda i:int(i)+1,readline().split()))

    H += 4
    W += 4

    dist = [-1]*(W*H)

    start = start[0]*W+start[1]
    goal = goal[0]*W+goal[1]

    for t,s in zip(count(2*W,W),read().split()):
        for i,c in zip(count(t+2),s.decode()):
            if c == '.':
                dist[i] = 10**7

    convert = lambda x,y: x*W+y
    CONVERTED_MOVES = []
    for d,l in MOVES:
        d = convert(*d)
        l = [convert(*d) for d in l]
        CONVERTED_MOVES.append((d,l))

    print(solve(dist,start,goal))

Submission status: Accepted

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

dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
q = deque()
# x, y, 累積移動距離, ブロック通過数, ワープ利用数
q.append((cx, cy, 0))
# visited = {}
visited = [[float("inf") for _ in range(W)] for _ in range(H)]
# visited[(cx, cy)] = 0
visited[cy][cx] = 0
ans = float("inf")
while q:
    x, y, c = q.popleft()
    # if (x, y) in visited and visited[(x, y)] < c:
    if visited[y][x] < c:
        # print("here1")
        continue
    # print(x, y, c, d, e)
    # for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
    for dx, dy in dirs:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            # if (nx, ny) in visited and visited[(nx, ny)] < c + 1:
            if visited[ny][nx] <= c:
                # print("here2")
                continue
            # visited[(nx, ny)] = c
            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
            # print("warp", dx, dy)
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                # print("warp append")
                # if (nx, ny) in visited and visited[(nx, ny)] < c + 1:
                if visited[ny][nx] < c + 1:
                    # print("here3")
                    continue
                # visited[(nx, ny)] = c + 1
                visited[ny][nx] = c + 1
                if nx == gx and ny == gy:
                    continue
                q.append((nx, ny, c+1))
# print(visited)
if visited[gy][gx] == float("inf"):
    print(-1)
else:
    print(visited[gy][gx])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


from collections import deque


# In[30]:


def main():
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    s = ["#"*(W+4)]
    s.append("#"*(W+4))
    for i in range(H):
        s.append("##"+input()+"##")
    s.append("#"*(W+4))
    s.append("#"*(W+4))
    
    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
    ch += 1; cw += 1
    dh += 1; dw += 1
    ans[ch][cw] = 0
    
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    magic = [
        [-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]
        ]
    
    mylist = deque([[ch,cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x,y = mylist.popleft()
        mylist2.append([x,y])
        for p,q in move:
            v1,v2 = x+p,y+q
            if ans[v1][v2] == -1:
                mylist.append([v1,v2])
                ans[v1][v2] = ans[x][y]
        if len(mylist) == 0:
            while len(mylist2) > 0:
                x2,y2 = mylist2.popleft()
                for v1,v2 in magic:
                    i,j = x2+v1,y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i,j])
    print(ans[dh][dw])

if __name__ == "__main__":
    main()


# In[31]:


# H,W = map(int, input().split())
# ch,cw = map(int, input().split())
# dh,dw = map(int, input().split())
# s = ["#"*(W+4)]
# s.append("#"*(W+4))
# for i in range(H):
#     s.append("##"+input()+"##")
# s.append("#"*(W+4))
# s.append("#"*(W+4))


# In[32]:


# 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
# ch += 1; cw += 1
# dh += 1; dw += 1
# ans[ch][cw] = 0


# In[33]:


# move = [[-1,0],[1,0],[0,-1],[0,1]]
# magic = [
#     [-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]
#     ]


# In[34]:


# mylist = deque([[ch,cw]])
# mylist2 = deque([])
# while len(mylist) > 0:
#     x,y = mylist.popleft()
#     mylist2.append([x,y])
#     for p,q in move:
#         v1,v2 = x+p,y+q
#         if ans[v1][v2] == -1:
#             mylist.append([v1,v2])
#             ans[v1][v2] = ans[x][y]
#     if len(mylist) == 0:
#         while len(mylist2) > 0:
#             x2,y2 = mylist2.popleft()
#             for v1,v2 in magic:
#                 i,j = x2+v1,y2+v2
#                 if ans[i][j] == -1:
#                     ans[i][j] = ans[x2][y2]+1
#                     mylist.append([i,j])
# print(ans[dh][dw])


# In[ ]:

Submission status: Accepted

Solution code:
from collections import deque
import sys

INF = 10 ** 8

H, W = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
MAP = []
for _ in range(H):
    MAP.append(list(input()))
d = [[INF for i in range(W)] for j in range(H)]
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]
tx_y = [(i, j) for i in range(-2, 3) for j in range(-2, 3)]

Q = deque()
Q.append([C[0]-1, C[1]-1, 0])

while len(Q) != 0:
    x, y, cnt = Q.popleft()
    
    if x == D[0]-1 and y == D[1]-1:
        print(cnt)
        sys.exit()
    
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt:
            d[nx][ny] = cnt
            Q.appendleft([nx, ny, cnt])
    
    for i, j in tx_y:
        nx = x + i
        ny = y + j
        if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt+1:
            d[nx][ny] = cnt+1
            Q.append([nx, ny, cnt+1])

print(-1)

Submission status: Accepted

Solution code:
# 参考: White_Pie_46
# https://atcoder.jp/contests/abc176/submissions/16168825
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)
    warp_can_reach = tuple(gen_warp_can_reach())
    qu = deque()
    qu.append((init_h, init_w, 0))  # 座標とワープ回数を保持

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if grid[h][w] == 'R':
            # 同じマスを複数回キューに追加しているかもしれない。
            # 短距離で調査済みなら再調査は不要。
            continue
        grid[h][w] = 'R'  # reached

        for h_delta, w_delta in adjacents:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    qu.appendleft((new_h, new_w, warps))

        for h_delta, w_delta in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    qu.append((new_h, new_w, warps + 1))
    return -1


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

Submission status: Accepted

Solution code:

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch, Cw, Dh, Dw = Ch - 1, Cw - 1, Dh - 1, Dw - 1
maze = [list(input()) for i in range(H)]
#print(maze)
  
ans = [[-1] * W for i in range(H)]  
ans[Ch][Cw] = 0
from collections import deque
q = deque([[0, Ch, Cw]])  
one = [[0, 1], [0, -1], [1, 0], [-1, 0]]
two = [[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 q:
  cnt, h, w = q.popleft()
  if ans[h][w] < cnt:
    continue
  for i, j in one:
    if (0 <= h + i < H) and (0 <= w + j < W) and (maze[h + i][w + j] != "#"):
        if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt:
          ans[h + i][w + j] = cnt
          q.appendleft([cnt, h + i, w + j])
  for i, j in two:  
    if (0 <= h + i < H) and (0 <= w + j < W) and (maze[h + i][w + j] != "#"):
        if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt + 1:
          ans[h + i][w + j] = cnt + 1
          q.append([cnt + 1, h + i, w + j])
              
print(ans[Dh][Dw])

Submission status: Accepted

Solution code:
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())
    c = [input().rstrip() for _ in range(h)]
    cw -= 1
    ch -= 1
    dw -= 1
    dh -= 1
    c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
    bfs = deque([[cw, ch]])
    warp_before = set()
    warp_after = set()

    for cnt in range(1000000):  # ワープ回数のカウント
        while bfs:  # ワープせずに歩いてどこまで行けるか
            for _ in range(len(bfs)):
                now_x, now_y = bfs.popleft()
                for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                    x, y = now_x + next_x, now_y + next_y
                    if 0 <= x < w and 0 <= y < h:
                        if x == dw and y == dh:
                            print(cnt)
                            exit()
                        c_next = c[y][x]
                        if c_next == "#":  # 壁の隣マスの座標をwarp_beforeに加える
                            warp_before.add((now_x, now_y))
                        if c_next == ".":  # 走査済マーク
                            c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                            bfs.append([x, y])
        else:
            if not warp_before:
                print(-1)
                exit()
            for now_x, now_y in warp_before:
                # 壁の隣マスの座標を中心に5*5マスの範囲で、壁の外側の未到達マスの座標をwarp_afterに加える
                if c[now_y][now_x] == "=":
                    for next_y in range(-2, 3):
                        for next_x in range(-2, 3):
                            x, y = now_x + next_x, now_y + next_y
                            if 0 <= x < w and 0 <= y < h:
                                warp_after.add((x, y))
            for x, y in warp_after:
                # 壁の外側の未到達マスの座標のゴール判定・走査済マーク「=」を付けてbfsに格納
                if c[y][x] == ".":
                    if x == dw and y == dh:  # 終了(ゴール)判定
                        print(cnt + 1)
                        exit()
                    c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                    bfs.append([x, y])
            warp_before = set()
            warp_after = set()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
path = [[10**10]*w for i in range(h)]
maze = []
for _ in range(h):
  s = input()
  maze.append(s)

walk = [(0,1),(1,0),(-1,0),(0,-1)]
warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)]+walk]
Q = deque()
path[ch-1][cw-1]=0
Q.append((ch-1,cw-1,0))
while Q:
  hi,wi,c = Q.popleft()
  for i,j in walk:
    nh = i + hi
    nw = j + wi
    if 0<=nh<h and 0<=nw<w and maze[nh][nw]=='.' and path[nh][nw]>c:
      path[nh][nw] = c
      Q.appendleft((nh,nw,c))
  for i,j in warp:
    nh = i + hi
    nw = j + wi
    if 0<=nh<h and 0<=nw<w and maze[nh][nw]=='.' and path[nh][nw]>c+1:
      path[nh][nw] = c+1
      Q.append((nh,nw,c+1))
print(path[dh-1][dw-1] if path[dh-1][dw-1]<10**10 else -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", "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_coordinate(self, h: int, w: int) -> int:
        return self.width * (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 = (-w, w, -1, 1)
        warp = [-2 * w - 2, -2 * w - 1, -2 * w, -2 * w + 1, -2 * w + 2]
        warp.extend([-w - 2, -w - 1, -w + 1, -w + 2, -2, 2])
        warp.extend([w - 2, w - 1, w + 1, w + 2])
        warp.extend([2 * w - 2, 2 * w - 1, 2 * w, 2 * w + 1, 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]

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

            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
#----------[入力受取・初期設定]----------#
H, W = map(int, input().split())
C = tuple(map(int, input().split())) # 魔法の位置
D = tuple(map(int, input().split())) # ゴール
D_y = D[0] -1 # 0スタート
D_x = D[1] -1 # 0スタート
S = [list(input()) for _ in range(H)]
visited = [[-1] * W for _ in range(H)]
visited[C[0]-1][C[1]-1] = 0 # 初期値
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)] # 普通の移動
main_q = deque()
magic_q = deque() # マジック用のキュー
main_q.append((C[0]-1, C[1]-1))
#----------[BFS]----------#
while main_q:
    y, x = main_q.pop()
    magic_q.append((y, x))
    for move in moves:
        dy, dx = move
        moved_y = y + dy
        moved_x = x + dx

        if moved_y < 0 or H -1 < moved_y or moved_x < 0 or W -1 < moved_x:
            continue
        if S[moved_y][moved_x] == '#':
            continue
        if S[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
            main_q.append((moved_y, moved_x))
            visited[moved_y][moved_x] = visited[y][x]
    #----------[マジック用のBFS]----------#
    if not main_q: # main_qが空になった場合は探索済みからマジックを使う
        while magic_q:
            y, x = magic_q.pop()
            for dy in range(-2, 3):
                for dx in range(-2, 3):
                    moved_y = y + dy
                    moved_x = x + dx

                    if moved_y < 0 or H -1 < moved_y or moved_x < 0 or W -1 < moved_x:
                        continue
                    if S[moved_y][moved_x] == '#':
                        continue
                    if S[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
                        main_q.append((moved_y, moved_x))
                        visited[moved_y][moved_x] = visited[y][x] + 1
#----------[回答表示]----------#
answer = visited[D_y][D_x]
print(answer)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input() for _ in range(H)]

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

while que:
    i, j = que.popleft()
    d = dist[i][j]
    for ni, nj in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
        if 0 <= ni < H and 0 <= nj < W:
            if S[ni][nj] == '.' and d < dist[ni][nj]:
                dist[ni][nj] = d
                que.appendleft((ni, nj))
    # magic
    nd = d+1
    for a in range(-2, 3):
        for b in range(-2, 3):
            ni, nj = i+a, j+b
            if 0 <= ni < H and 0 <= nj < W:
                if S[ni][nj] == '.' and nd < dist[ni][nj]:
                    dist[ni][nj] = nd
                    que.append((ni, nj))

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

Submission status: Accepted

Solution code:
#----------[インポート]----------#
from collections import deque

def main():
    #----------[入力受取・初期設定]----------#
    H, W = map(int, input().split())
    C = tuple(map(int, input().split())) # 魔法の位置
    D = tuple(map(int, input().split())) # ゴール
    D_y = D[0] -1 # 0スタート
    D_x = D[1] -1 # 0スタート
    S = [list(input()) for _ in range(H)]
    visited = [[-1] * W for _ in range(H)]
    visited[C[0]-1][C[1]-1] = 0 # 初期値
    moves = [(1, 0), (0, 1), (-1, 0), (0, -1)] # 普通の移動
    main_q = deque()
    magic_q = deque() # マジック用のキュー
    main_q.append((C[0]-1, C[1]-1))
    # magic_q.append((C[0]-1, C[1]-1))

    #----------[BFS]----------#
    while main_q:
        y, x = main_q.pop()
        magic_q.append((y, x))
        for move in moves:
            dy, dx = move
            moved_y = y + dy
            moved_x = x + dx

            if moved_y < 0 or H -1 < moved_y or moved_x < 0 or W -1 < moved_x:
                continue
            if S[moved_y][moved_x] == '#':
                continue
            if S[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
                main_q.append((moved_y, moved_x))
                visited[moved_y][moved_x] = visited[y][x]

        #----------[マジック用のBFS]----------#
        if not main_q: # main_qが空になった場合は探索済みからマジックを使う
            while magic_q:
                y, x = magic_q.pop()
                for dy in range(-2, 3):
                    for dx in range(-2, 3):
                        moved_y = y + dy
                        moved_x = x + dx

                        if moved_y < 0 or H -1 < moved_y or moved_x < 0 or W -1 < moved_x:
                            continue
                        if S[moved_y][moved_x] == '#':
                            continue
                        if S[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
                            main_q.append((moved_y, moved_x))
                            visited[moved_y][moved_x] = visited[y][x] + 1

    answer = visited[D_y][D_x]
    print(answer)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit, i8, b1
import heapq

@njit(i8(b1[:,:],i8,i8,i8,i8),cache=True)
def solve(road_map,ch,cw,dh,dw):

    h,w = road_map.shape
    queue = [(0,ch*w+cw)]
    max_l = 2<<30
    used_map = np.full(h*w,max_l,dtype=np.int64)
    goal = dh*w+dw
    used_map[ch*w+cw] = 0

    #move walk
            
    while len(queue) != 0:
        tl,n = heapq.heappop(queue)
        th,tw = divmod(n,w)
        if n == goal:
            break

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if x == y == 0:
                    continue
                if abs(x)+abs(y) <= 1:
                    loop = tl
                else:
                    loop = tl+1
                tx = th + x
                ty = tw + y
                next_n  = tx*w+ty
                if tx < 0 or ty < 0 or tx >= h or ty >= w or road_map[tx][ty] == True:
                    continue
                check = used_map[next_n]
                if check > loop:
                    used_map[next_n] = loop
                    heapq.heappush(queue,(loop,next_n))

    ans = used_map[goal]
    if ans == max_l:
        return -1
    else:
        return ans

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

print(solve(road_map,ch,cw,dh,dw))

Submission status: Accepted

Solution code:
#shotoyooさんのコードをお借りしてテスト

import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
      

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
ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))

Submission status: Accepted

Solution code:
from itertools import product
from collections import deque
H,W=list(map(int, input().split()))
C=list(map(int, input().split()))
D=list(map(int, input().split()))
S=[list(input()) for _ in range(H)]
# print(S)
C[0]-=1
C[1]-=1
D[0]-=1
D[1]-=1

a=[-2,-1,0,1,2]
wk={(1,0),(-1,0),(0,1),(0,-1)}
wp=set(product(a,a)).difference(wk)
wp-={(0,0)}

stk=deque([[C[0],C[1],0]])
dp=[[float('inf')]*W for _ in range(H)]

def BFS():
    while len(stk)>0:
        l=stk.pop()
        i=l[0]
        j=l[1]
        ct=l[2]
        if ct>=dp[i][j]:
            continue
        dp[i][j]=ct
        for k in wk:
            x=i+k[0]
            y=j+k[1]
            if 0<=x<H and 0<=y<W and S[x][y]=='.':
                stk.append([x,y,ct])
        for k in wp:
            x=i+k[0]
            y=j+k[1]
            if 0<=x<H and 0<=y<W and S[x][y]=='.':
                stk.appendleft([x,y,ct+1])

BFS()
# print(dp)
ans=dp[D[0]][D[1]]
if ans ==float('inf'):
    print(-1)
else:
    print(dp[D[0]][D[1]])