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
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_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
        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] == unsearched or 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] == unsearched or dist[nx] > cur_dist + 1:
                    dist[nx] = cur_dist + 1
                    queue.append(nx)

        return dist[self.goal]

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

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_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)
    
    print(maze.bfs())


if __name__ == "__main__":
    main()

Solution (Python):

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 
D_x = D[1] -1 
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))

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

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

Solution (Python):

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 
    D_x = D[1] -1 
    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))
    

    
    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]

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

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

    
            
    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=="

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

Solution (Python):


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
        
                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=="

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

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

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

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

Solution (Python):
H,W=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
S=[input() for i in range(H)]
from collections import deque
q=deque([(ch-1,cw-1,0)])
v=[[9**9]*W for i in range(H)]
x=((1,0),(-1,0),(0,-1),(0,1))
y=((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:
    h,w,d=q.popleft()
    for i,j in x:
        if 0<=h+i<H and 0<=w+j<W and S[h+i][w+j]=='.' and d<v[h+i][w+j]:
            v[h+i][w+j]=d
            q.appendleft((h+i,w+j,d))
    for i,j in y:
        if 0<=h+i<H and 0<=w+j<W and S[h+i][w+j]=='.' and d+1<v[h+i][w+j]:
            v[h+i][w+j]=d+1
            q.append((h+i,w+j,d+1))
print(v[dh-1][dw-1] if v[dh-1][dw-1]<9**9 else -1)

Solution (Python):
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 = [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))
    distances = [[-1] * width for _ in range(height)]
    
    arrived_total = set()
    arrived_total.add((init_h, init_w))
    warp_count = 0

    def append_qu(now_h, now_w, next_go_to):
        """行き先へ進めそうならキューに追加し， arrived_total に記録する。"""
        for h_delta, w_delta in next_go_to:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if (new_h, new_w) in arrived_total:
                continue
            if grid[new_h][new_w] == '
                arrived_total.add((new_h, new_w))
                continue
            qu.append((new_h, new_w))
            arrived_total.add((new_h, new_w))

    while qu:
        arrived_set_by_cost = set()
        
        while qu:
            h, w = qu.popleft()
            if h == dest_h and w == dest_w:
                return warp_count
            distances[h][w] = warp_count
            arrived_set_by_cost.add((h, w))
            append_qu(h, w, adjacents)

        warp_count += 1
        
        for h, w in arrived_set_by_cost:
            append_qu(h, w, warp_can_reach)

    return distances[dest_h][dest_w]


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

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


def main():
    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 = ["
    s.append("
    for i in range(h):
        s.append("
    s.append("
    s.append("
    
    
    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
    ans[ch][cw] = 0
    
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    move2 = [(-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)]
        
    not_yet = [(ch, cw)]
    one_time = []
    
    while len(not_yet) > 0:
        x, y = not_yet.pop()
        one_time.append((x, y))
        for (p, q) in move:
            v1, v2 = x+p, y+q
            if ans[v1][v2] == -1:
                not_yet.append((v1, v2))
                ans[v1][v2] = ans[x][y]
                
        if len(not_yet) == 0:
            while len(one_time) > 0:
                x2, y2 = one_time.pop()
                for (v1, v2) in move2:
                    i, j = x2+v1, y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        not_yet.append((i, j))
          
    print(ans[dh][dw])
    
    
    
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

H,W=map(int,input().split())

array_st=list(map(int,input().split()))
array_gl=list(map(int,input().split()))
start_point=[]
goal_point=[]
for i in range(2):
    start_point.append(array_st[i]-1)
    goal_point.append(array_gl[i]-1)

matrix=[]
for i in range(H):
    matrix.append(list(input()))

d=deque()
d.append([start_point[0],start_point[1],0])

road=[-1,1]

ans=-1
while d:
    v=d.popleft()
    if matrix[v[0]][v[1]]=="x":
        continue
    matrix[v[0]][v[1]]="x"
    if [v[0],v[1]]==goal_point:
        ans=v[2]
        break
    for i in road:
        if v[0]+i>=0 and v[0]+i<H:
            if matrix[v[0]+i][v[1]]==".":
                d.appendleft([v[0]+i,v[1],v[2]])
        if v[1]+i>=0 and v[1]+i<W:
            if matrix[v[0]][v[1]+i]==".":
                d.appendleft([v[0],v[1]+i,v[2]])

    for i in range(-2,3):
        for j in range(-2,3):
            if v[0]+i>=0 and v[0]+i<H:
                if v[1]+j>=0 and v[1]+j<W:
                    if matrix[v[0]+i][v[1]+j]==".":
                        d.append([v[0]+i,v[1]+j,v[2]+1])

print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = (ch,cw)
goal = (dh,dw)
seen = [None]*n
seen[start[0]*w+start[1]] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] 


dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,(ux,uy) = hpp(q)
    if (ux,uy)==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 = 1
            else:
                vv = 0
            x = ux+xx
            y = uy+yy
            num = pnum+vv
            if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="
                continue            
            if seen[x*w+y] is None or seen[x*w+y]>num:
                seen[x*w+y] = num
                hp(q, (num, (x,y)))
val = seen[goal[0]*w+goal[1]]
if val is None:
    print(-1)
else:
    print(val)

Solution (Python):
from collections import deque

def main():
    h, w = map(int, input().split())
    start_h, start_w = map(lambda x: int(x)+1, input().split())
    goal_h, goal_w = map(lambda x: int(x)+1, input().split())

    s = ["
    s.append("
    for _ in range(h):
        s.append("
    s.append("
    s.append("

    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
    ans[start_h][start_w] = 0

    move1 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    move2 = [(-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)]

    yet = deque([(start_h, start_w)])
    done = deque()

    while yet:
        x1, y1 = yet.popleft()
        done.append((x1, y1))
        for (p, q) in move1:
            v1, v2 = x1+p, y1+q
            if ans[v1][v2] == -1: 
                yet.append((v1, v2))
                ans[v1][v2] = ans[x1][y1]

        if len(yet) == 0:
            while done:
                x2, y2 = done.popleft()
                for (p, q) in move2:
                    i, j = x2+p, y2+q
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        yet.append((i, j))

    print(ans[goal_h][goal_w])

if __name__ == "__main__":
    main()

Solution (Python):
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 = [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))
    arrived_total = set()
    arrived_total.add((init_h, init_w))
    distances = [[-1] * width for _ in range(height)]
    warp_count = 0

    def append_qu(now_h, now_w, next_go_to):
        """行き先へ進めそうならキューに追加し， arrived_total に記録する。"""
        for h_delta, w_delta in next_go_to:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if (new_h, new_w) in arrived_total:
                continue
            if grid[new_h][new_w] == '
                arrived_total.add((new_h, new_w))
                continue
            qu.append((new_h, new_w))
            arrived_total.add((new_h, new_w))

    while qu:
        arrived_set_by_cost = set()
        
        while qu:
            h, w = qu.popleft()
            distances[h][w] = warp_count
            arrived_set_by_cost.add((h, w))
            append_qu(h, w, adjacents)

        warp_count += 1
        
        for h, w in arrived_set_by_cost:
            append_qu(h, w, warp_can_reach)

    return distances[dest_h][dest_w]


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

Solution (Python):
from collections import deque

h, w = map(int, input().split())
start_h, start_w = map(int, input().split())
goal_h, goal_w = map(int, input().split())

start_h += 1
start_w += 1
goal_h += 1
goal_w += 1

s = ["
s.append("
for _ in range(h):
    s.append("
s.append("
s.append("

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
ans[start_h][start_w] = 0

move1 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
move2 = [(-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)]

yet = deque([(start_h, start_w)])
done = deque()

while len(yet) > 0:
    x1, y1 = yet.popleft()
    done.append((x1, y1))
    for (p, q) in move1:
        v1, v2 = x1+p, y1+q
        if ans[v1][v2] == -1: 
            yet.append((v1, v2))
            ans[v1][v2] = ans[x1][y1]

    if len(yet) == 0:
        while len(done) > 0:
            x2, y2 = done.popleft()
            for (p, q) in move2:
                i, j = x2+p, y2+q
                if ans[i][j] == -1:
                    ans[i][j] = ans[x2][y2]+1
                    yet.append((i, j))

print(ans[goal_h][goal_w])

Solution (Python):


import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines

h,w=map(int,input().split())
nx,ny=map(int,input().split())
gx,gy=map(int,input().split())
maze=inputs()

nx-=1;ny-=1;gx-=1;gy-=1
from collections import deque

dq=deque([(nx,ny)])
dq2=deque([])

T=[[float('inf')]*w for  a in range(h)]

T[nx][ny]=0

moves=((1,0),(-1,0),(0,1),(0,-1))
from itertools import product as pr

Mmoves=tuple(i for i in pr((-2,-1,0,1,2),repeat=2)if i!=(0,0) )

while dq:
    
    while dq:
        x,y=dq.popleft()
        for i,j in moves:
            nex,ney=x+i,y+j
            
            if not(0<=nex<h and 0<=ney<w) or maze[nex][ney]==35:continue
            if T[x][y]<T[nex][ney]:
                
                T[nex][ney]=T[x][y]
                dq.append((nex,ney))
        for i,j in Mmoves:
            nex,ney=x+i,y+j
            if not(0<=nex<h and 0<=ney<w) or maze[nex][ney]==35:continue
            if T[x][y]+1<T[nex][ney]:
                T[nex][ney]=T[x][y]+1
                dq2.append((nex,ney))
    
    dq,dq2=dq2,dq
if T[gx][gy]==float('inf'):print(-1)
else:print(T[gx][gy])

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)





from collections import deque



INF = 1 << 50

def bfs(MAZE, start, goal):
    H = len(MAZE)
    W = len(MAZE[0])
    MAP = [[INF] * W for _ in range(H)]
    walks = [(0,1), (1,0), (-1,0), (0, -1)]
    warps = []
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == 0 and j == 0: continue
            if not (i,j) in walks:
                warps.append((i, j))
    queue = deque([])
    k = (0,) + start
    queue.append(k)

    while queue:
        count, ci, cj = queue.pop()
        if (ci, cj) == goal:
            return count
        for ii, jj in walks:
            ni, nj = ci + ii, cj + jj
            if MAZE[ni][nj] == '.' and MAP[ni][nj] > count:
                queue.append((count, ni, nj))
                MAP[ni][nj] = count
        for ii, jj in warps:
            ni, nj = ci + ii, cj + jj
            if MAZE[ni][nj] == '.' and MAP[ni][nj] > count+1:
                queue.appendleft((count+1, ni, nj))
                MAP[ni][nj] = count + 1
    return -1


def run():
    H, W = map(int, sysread().split())
    Ci, Cj = map(int, sysread().split())
    Ci += 1
    Cj += 1
    Di, Dj = map(int, sysread().split())
    Di += 1
    Dj += 1
    MAZE = []
    MAZE.append('
    MAZE.append('
    for i in range(H):
        s = input()
        s = '
        MAZE.append(s)
    MAZE.append('
    MAZE.append('
    print(bfs(MAZE, (Ci, Cj), (Di, Dj)))

if __name__ == "__main__":
    run()

Solution (Python):
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
h,w=map(int,input().split())
nx,ny=map(int,input().split())
gx,gy=map(int,input().split())
maze=[input()for i in range(h)]

nx-=1;ny-=1;gx-=1;gy-=1
from collections import deque
dq=deque([(nx,ny)])
dq2=deque([])
T=[[float('inf')]*w for  a in range(h)]
T[nx][ny]=0
moves=((1,0),(-1,0),(0,1),(0,-1))
from itertools import product as pr
Mmoves=tuple(i for i in pr((-2,-1,0,1,2),repeat=2)if i!=(0,0) )

while dq:
    while dq:
        x,y=dq.popleft()
        for i,j in moves:
            nex,ney=x+i,y+j
            if not(0<=nex<h and 0<=ney<w) or maze[nex][ney]==35:continue
            if T[x][y]<T[nex][ney]:
                T[nex][ney]=T[x][y]
                dq.append((nex,ney))
        for i,j in Mmoves:
            nex,ney=x+i,y+j
            if not(0<=nex<h and 0<=ney<w) or maze[nex][ney]==35:continue
            if T[x][y]+1<T[nex][ney]:
                T[nex][ney]=T[x][y]+1
                dq2.append((nex,ney))
    dq,dq2=dq2,dq
if T[gx][gy]==float('inf'):print(-1)
else:print(T[gx][gy])