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

Submission status: Accepted

Solution code:
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 * self.threshold + Y, 0))

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

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

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] == '#': continue
        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] == '#': continue
                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)

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", "unsearched", "dist"]

    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.dist = self._convert_grid_to_dist(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 _convert_grid_to_dist(self, grid: List[bytes]) -> 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 == self.road:
                    dist[i] = self.unsearched
            i += 4
        return dist

    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:
            next_queue = deque()
            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.append(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
                            next_queue.append(nx)
            queue = next_queue

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

Submission status: Accepted

Solution code:
from collections import deque
inf = 10**10
dxdy = ((0,1),(0,-1),(1,0),(-1,0)) 
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = ['#'*(w+2)] + ['#' + input() + '#' for _ in range(h)] + ['#'*(w+2)]
d = [[inf]*(w+1) for _ in range(h+1)]
d[ch][cw] = 0
q = deque([(ch,cw)])
while q: 
    y,x = q.pop() 
    for dx,dy in dxdy: 
        if s[y+dy][x+dx]=='.' and d[y+dy][x+dx] > d[y][x]:
            d[y+dy][x+dx] = d[y][x]
            q.append((y+dy,x+dx))
    for i in range(-2,3):
        for j in range(-2,3):
            if i==j==0:
                continue 
            elif 1<=y+i<=h and 1<=x+j<=w and s[y+i][x+j]=='.' and d[y+i][x+j]>d[y][x]+1:
                
                d[y+i][x+j] = d[y][x]+1
                q.appendleft((y+i,x+j)) 
ans = d[dh][dw] 
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
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()))
# ---------標準入力時--------------

ch-=1; cw-=1; dh-=1; dw-=1

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

for i in range(h):
    m[i] = ['#']*2 + m[i] + ['#']*2
    
m = [['#']*(w+4)]*2 + m + [['#']*(w+4)]*2
ch+=2; cw+=2; dh+=2; dw+=2

def bfs4():
    '''
    bfs3とほぼ同じ. 迷路の上下左右に2列ずつ壁追加
    '''
    que1=[]
    que2=[] # queueというよりはメモリ
    m[ch][cw]=str(0)
    que1.append((ch,cw))

    while que1!=[]:
        l1=len(que1)
        r1=0 # que1における使用済みindex

        # que1の要素(座標)から歩いていけるマス
        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:
            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=[]
###---------------------------------------

bfs4()


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

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", "unsearched", "dist"]

    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.dist = self._convert_grid_to_dist(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 _convert_grid_to_dist(self, grid: List[bytes]) -> 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 == self.road:
                    dist[i] = self.unsearched
            i += 4
        return dist

    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 debug(self):
        print("<DEBUG>", file=sys.stderr)
        for row in zip(*[iter(self.dist)] * 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))
    # maze.debug()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
ch, cw =  map(int, input().split())
gh, gw =  map(int, input().split())

f = [[s=="." for s in input()] for h in range(H)]
ans = [[-1 for w in range(W)]for h in range(H)]

nextQ = [(ch-1)*1000 + cw-1]
ans[ch-1][cw-1] = 0
while len(nextQ)>0:
  Q = list(nextQ)
  nextQ = set()
  i = 0
  while i<len(Q):
    nh = Q[i]
    i += 1
    nw = nh%1000
    nh = nh//1000
    for dh in range(0-min(nh,2), 3):
      if nh+dh>=H:
        break
      for dw in range(0-min(nw,2), 3):
        if nw + dw>=W:
          break
        if dh==0 and dw==0:
          continue
        if dh*dw==0 and (abs(dh)==1 or abs(dw)==1):
          if ans[nh+dh][nw+dw]==-1:
            if f[nh+dh][nw+dw]:
              Q.append((nh+dh)*1000 + nw+dw)
              ans[nh+dh][nw+dw]=ans[nh][nw]
            else:
              ans[nh+dh][nw+dw]=-2
          elif ans[nh+dh][nw+dw]>ans[nh][nw]:
            Q.append((nh+dh)*1000 + nw+dw)
            nextQ -= {(nh+dh)*1000 + nw+dw}
            ans[nh+dh][nw+dw]=ans[nh][nw]
        else:
          if ans[nh+dh][nw+dw]==-1:
            if f[nh+dh][nw+dw]:
              nextQ.add((nh+dh)*1000 + nw+dw)
              ans[nh+dh][nw+dw]=ans[nh][nw]+1
            else:
              ans[nh+dh][nw+dw]=-2

print(ans[gh-1][gw-1])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
ch, cw =  map(int, input().split())
gh, gw =  map(int, input().split())

f = [[s=="." for s in input()] for h in range(H)]
ans = [[-1 for w in range(W)]for h in range(H)]

nextQ = [(ch-1)*1000 + cw-1]
ans[ch-1][cw-1] = 0
while len(nextQ)>0:
  Q = list(nextQ)
  nextQ = set()
  visited = set()
  while len(Q):
    nh = Q.pop(0)
    nw = nh%1000
    nh = nh//1000
    for dh in range(0-min(nh,2), 3):
      if nh+dh>=H:
        break
      for dw in range(0-min(nw,2), 3):
        if nw + dw>=W:
          break
        if dh==0 and dw==0:
          continue
        if dh*dw==0 and (abs(dh)==1 or abs(dw)==1):
          if ans[nh+dh][nw+dw]==-1:
            if f[nh+dh][nw+dw]:
              Q.append((nh+dh)*1000 + nw+dw)
              visited.add((nh+dh)*1000 + nw+dw)
              ans[nh+dh][nw+dw]=ans[nh][nw]
            else:
              ans[nh+dh][nw+dw]=-2
          elif ans[nh+dh][nw+dw]>ans[nh][nw]:
            Q.append((nh+dh)*1000 + nw+dw)
            nextQ -= {(nh+dh)*1000 + nw+dw}
            ans[nh+dh][nw+dw]=ans[nh][nw]
        else:
          if ans[nh+dh][nw+dw]==-1:
            if f[nh+dh][nw+dw]:
              nextQ.add((nh+dh)*1000 + nw+dw)
              ans[nh+dh][nw+dw]=ans[nh][nw]+1
            else:
              ans[nh+dh][nw+dw]=-2
print(ans[gh-1][gw-1])

Submission status: Accepted

Solution code:
def main():
    from collections import deque

    h, w = map(int, input().split())
    start = tuple(map(lambda x: int(x) - 1, input().split()))
    goal = tuple(map(lambda x: int(x) - 1, input().split()))

    maze = tuple([tuple(input()) for _ in range(h)])
    vis = [[False] * w for _ in range(h)]

    mw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    mj = list(set((i, j) for i in range(-2, 3) for j in range(-2, 3)) - set(mw) - {(0, 0)})

    q = deque()
    q.append((start[0], start[1], 0))
    while q:
        y, x, c = q.popleft()
        if vis[y][x]:
            continue
        vis[y][x] = True
        if (y, x) == goal:
            print(c)
            break
        for a, b in mw:
            if 0 <= y + a < h and 0 <= x + b < w:
                if maze[y + a][x + b] == '.':
                    q.appendleft((y + a, x + b, c))
        for a, b in mj:
            if 0 <= y + a < h and 0 <= x + b < w:
                if maze[y + a][x + b] == '.':
                    q.append((y + a, x + b, c + 1))
    else:
        print(-1)


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())
Ch,Cw,Dh,Dw = Ch-1,Cw-1,Dh-1,Dw-1
S = []
for i in range(H):
    S.append(list(input()))


def check(h,w):
    if 0<=h<=H-1 and 0<=w<=W-1:
        if S[h][w] == ".":
            return True
    return False

def move_A():
    v = [[-1,0],[1,0],[0,1],[0,-1]]
    while qA != deque():
        h,w,c = map(int,qA.pop())
        searched[h][w] = True
        qB.append([h,w,c])
        for vv in v:
            next_h = h+vv[0]
            next_w = w+vv[1]
            if check(next_h,next_w) and searched[next_h][next_w] == False:
                qA.append([next_h,next_w,c])
                cost[next_h][next_w] = c

def move_B():
    while qB != deque():
        h,w,c = map(int,qB.pop())
        for i in range(-2,3):
            for j in range(-2,3):
                next_h = h + i
                next_w = w + j
                if check(next_h,next_w) and searched[next_h][next_w] == False:
                    qA.append([next_h,next_w,c+1])
                    searched[next_h][next_w] = True
                    cost[next_h][next_w] = c+1
        
searched = [[False]*W for _ in range(H)]
cost = [[10**9]*W for _ in range(H)]

qA = deque()
qB = deque()
qA.append([Ch,Cw,0])
cost[Ch][Cw] = 0

while qA != deque():
    move_A()
    move_B()

if searched[Dh][Dw] == False:
    print(-1)
else:
    print(cost[Dh][Dw])

Submission status: Accepted

Solution code:
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] == '#' or V[h][w] != -1:
                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]))
    
    # 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])

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

    dist = [-1] * vertex
    dist[start_area_num] = 0
    q = deque()
    q.append((start_area_num,0))
    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 dist[next_area_num] == -1:
                dist[next_area_num] = dist[cur_area_num] + 1
                q.append((next_area_num,0))
    else:
        print(-1)

if __name__ == '__main__':
    solve()