Problem:
 Score : 400 points    Problem Statement A maze is composed of a grid of H \times W squares - H vertical, W horizontal.  The square at the i -th row from the top and the j -th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is . .  There is a magician in (C_h,C_w) . He can do the following two kinds of moves:   Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.  Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.   In either case, he cannot go out of the maze.  At least how many times does he need to use the magic to reach (D_h, D_w) ?      Constraints  1 \leq H,W \leq 10^3  1 \leq C_h,D_h \leq H  1 \leq C_w,D_w \leq W  S_{ij} is # or . .  S_{C_h C_w} and S_{D_h D_w} are . .  (C_h,C_w) \neq (D_h,D_w)         Input Input is given from Standard Input in the following format:  H  W  C_h  C_w  D_h  D_w  S_{11}\ldots S_{1W}  \vdots  S_{H1}\ldots S_{HW}       Output Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w) , print -1 instead.        Sample Input 1 4 4
1 1
4 4
..#.
..#.
.#..
.#..      Sample Output 1 1  For example, by walking to (2,2) and then using the magic to travel to (4,4) , just one use of magic is enough.  Note that he cannot walk diagonally.       Sample Input 2 4 4
1 4
4 1
.##.
####
####
.##.      Sample Output 2 -1  He cannot move from there.       Sample Input 3 4 4
2 2
3 3
....
....
....
....      Sample Output 3 0  No use of magic is needed.       Sample Input 4 4 5
1 2
2 5
#.###
####.
#..##
#..##      Sample Output 4 2

Solution (Python):
import sys, math
import io, os


from heapq import heapify, heappush, heappop


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


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


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

queue = [(0, (ch, cw))]
while queue:
    path_len, (u, v) = heappop(queue)
    if path_len == 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 path_len < dist[u+i][v+j]:
                            dist[u+i][v+j] = path_len
                            heappush(queue, (path_len, (u+i, v+j)))
                    else:
                        if 1 + path_len < dist[u + i][v + j]:
                            dist[u + i][v + j] = 1 + path_len
                            heappush(queue, (1 + path_len, (u + i, v + j)))


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

Solution (Python):
import heapq

H, W = map(lambda x: int(x)+4, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

grid = '
for _ in range(H-4):
  grid += '
grid += '

move_list = []
for i in range(5):
  for j in range(5):
    if (i, j) == (2, 2):
      continue
    elif (i, j) == (1, 2) or (i, j) == (2, 1) or (i, j) == (2, 3) or (i, j) == (3, 2):
      move_list.append((0, i-2 + W*(j-2)))
    else:
      move_list.append((1, i-2 + W*(j-2)))

def dijkstra(s):
  hq = [(0, s)]
  heapq.heapify(hq)
  cost = [float("inf")] * (H*W)
  cost[s] = 0
  while hq:
    c, v = heapq.heappop(hq)
    if c > cost[v]:
      continue
    for dc, dv in move_list:
      w = v + dv
      tmp = cost[v] + dc
      if grid[w] == "
        continue
      if tmp < cost[w]:
        cost[w] = tmp
        heapq.heappush(hq, (tmp, w))
  return cost

ans = dijkstra( (Ch+1)*W + Cw+1 )[(Dh+1)*W + Dw+1]

if ans == float("inf"):
  print(-1)
else:
  print(ans)

Solution (Python):


H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
S=[None]*H
for i in range(H):
    S[i] = input()

from collections import deque
def in_area(x,y):
    return 0<=x<=H-1 and 0<=y<=W-1
    
def cango_step(x,y):
    cand0 =[(x+1,y),(x-1,y),(x,y+1),(x,y-1)]
    cand=[c for c in cand0 if in_area(*c)]
    return cand

def cango_warponly(x,y):
    cand0 =[(x-2,y-2),(x-2,y-1),(x-2,y),(x-2,y+1),(x-2,y+2),
            (x+2,y-2),(x+2,y-1),(x+2,y),(x+2,y+1),(x+2,y+2),
            (x+1,y-2),(x,y-2),(x-1,y-2),
            (x+1,y+2),(x,y+2),(x-1,y+2),
            (x+1,y+1),(x+1,y-1),(x-1,y+1),(x-1,y-1)]
    cand=[c for c in cand0 if in_area(*c)]
    return cand

q = deque([(-1,-1,CH-1,CW-1,0)]) 
been = [[False]*W for _ in range(H)]
INF=10**20
shortest =[[INF]*W for _ in range(H)]
shortest[CH-1][CW-1] = 0
    
reach=False
while q:
    x_old,y_old,x_now,y_now,time = q.pop()
    
    



        
    cand = cango_step(x_now,y_now)
    for x_new,y_new in cand:
        if S[x_new][y_new]=="." and shortest[x_new][y_new]>time:
            q.append((x_now,y_now,x_new,y_new,time))
            shortest[x_new][y_new]=time
            
    cand = cango_warponly(x_now,y_now)
    for x_new,y_new in cand:
        if S[x_new][y_new]=="." and shortest[x_new][y_new]>time+1:
            q.appendleft((x_now,y_now,x_new,y_new,time+1))
            shortest[x_new][y_new]=time+1
            
if shortest[DH-1][DW-1]==INF:
    print(-1)
else:
    print(shortest[DH-1][DW-1])

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


cnt=[[-1]*w for _ in range(h)]
cnt[ch][cw]=0
from collections import deque

q=deque()
q2=deque()
q.append((ch,cw))
d=[(1,0),(-1,0),(0,1),(0,-1)]
d2=[(i-2,j-2) for i in range(5) for j in range(5)]
tmp=0
while q2 or q:
    while q:
        y,x=q.popleft()
        q2.append((y,x))
        for dx,dy in d:
            if 0<=y+dy<=h-1 and 0<=x+dx<=w-1 and  s[y+dy][x+dx]=="." and cnt[y+dy][x+dx]<0:
                cnt[y+dy][x+dx]=cnt[y][x]
                q.append((y+dy,x+dx))
    y,x=q2.popleft()
    tmp+=1
    for dx,dy in d2:
        
        if 0<=y+dy<=h-1 and 0<=x+dx<=w-1 and  s[y+dy][x+dx]=="." and cnt[y+dy][x+dx]<0:
            cnt[y+dy][x+dx]=cnt[y][x]+1
            q.append((y+dy,x+dx))

print(cnt[dh][dw])

Solution (Python):
from collections import deque

H, W = map(lambda x: int(x)+4, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

grid = '
for _ in range(H-4):
  grid += '
grid += '

magic_list = []
for i in range(5):
  for j in range(5):
    if (i, j) in [(2, 2), (1, 2), (2, 1), (2, 3), (3, 2)]:
      continue
    else:
      magic_list.append(i-2 + W*(j-2))

move_list = [-1, 1, W, -W]

def bfs(start):
  INF = 10 ** 9
  dist = [INF] * (H*W)
  dist[start] = 0
  q = deque([start])
  while q:
    v = q.popleft()
    dv = dist[v]
    for move in move_list:
      w = v + move
      if grid[w] == '
        continue
      dw = dv
      if dw >= dist[w]:
        continue
      dist[w] = dw
      q.appendleft(w)
    for magic in magic_list:
      w = v + magic
      if grid[w] == '
        continue
      dw = dv + 1
      if dw >= dist[w]:
        continue
      dist[w] = dw
      q.append(w)
  return dist

ans = bfs( (Ch+1)*W + Cw+1 )[(Dh+1)*W + Dw+1]

if ans == 10**9:
  print(-1)
else:
  print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_map_as(H, replace={'
    '''
    文字列のmapを置換して読み込み。デフォでは
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            
            
    else:  
        ret = [[pad] * (W + 2)]  
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


def grid_dijkstra(grid, si: int, sj: int):
    '''grid上のdijkstra法。gridはそこに入るときにかかるコスト
    si,sj は開始の座標。'''
    from heapq import heappop, heappush
    H = len(grid)
    W = len(grid[0])
    D = [[-1] * W for _ in [0] * H]  
    que = [(0, si, sj)]
    while que:
        c, i, j = heappop(que)
        if D[i][j] != -1:
            continue
        D[i][j] = c
        for di, dj in product([-2, -1, 0, 1, 2], repeat=2):
            ni, nj = i + di, j + dj
            if not (0 <= ni < H and 0 <= nj < W) or D[ni][nj] != -1 or ni == nj == 0 or grid[ni][nj] == 1:
                continue
            if (di == 0 and abs(dj) == 1) or (dj == 0 and abs(di) == 1):  
                nc = c
            else:  
                nc = c + 1
            heappush(que, (nc, ni, nj))
    return D


MOD = 10**9 + 7
INF = 2**31  

from itertools import product, permutations, combinations
from collections import deque






H, W = ints()
si, sj = mina(*ints())
ti, tj = mina(*ints())

S = read_map_as(H)
D = [[-1] * W for _ in [0] * H]  
que = deque([(0, si, sj)])
while que:
    c, i, j = que.popleft()
    if D[i][j] != -1:
        continue
    D[i][j] = c
    for di, dj in product([-2, -1, 0, 1, 2], repeat=2):
        ni, nj = i + di, j + dj
        if not (0 <= ni < H and 0 <= nj < W) or D[ni][nj] != -1 or ni == nj == 0 or S[ni][nj] == 1:
            continue
        if (di == 0 and abs(dj) == 1) or (dj == 0 and abs(di) == 1):  
            que.appendleft((c, ni, nj))  
        else:  
            que.append((c + 1, ni, nj))  

print(D[ti][tj])

Solution (Python):




import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict


MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

import numpy as np
from numba import i8, njit, u1, b1
from heapq import heappop, heappush


def solve(grid, ch, cw, dh, dw):
    h, w = grid.shape
    
    dist = np.full((h, w), INF, dtype=np.int64)
    dist[ch][cw] = 0

    que = [(0, ch, cw)]

    while que:
        cnt, y, x = heappop(que)

        if y == dh and x == dw:
            break

        for dy in range(-2, 3):
            for dx in range(-2, 3):
                if dx == 0 and dy == 0:
                    continue

                if abs(dx) == 2 or abs(dy) == 2 or (abs(dx) == 1 and abs(dy) == 1):
                    warp = 1
                else:
                    warp = 0

                nx, ny = x + dx, y + dy
                if nx < 0 or nx >= w or ny < 0 or ny >= h or grid[ny][nx]:
                    continue
                
                if dist[ny][nx] > cnt + warp:
                    dist[ny][nx] = cnt + warp
                    heappush(que, (cnt + warp, ny, nx))

    if dist[dh][dw] == INF:
        return - 1
    else:
        return dist[dh][dw]


def Main():
    H, W = read_ints()
    ch, cw = read_ints(); ch -= 1; cw -= 1
    dh, dw = read_ints(); dh -= 1; dw -= 1

    grid = np.array([[g == '
    
    print(solve(grid, ch, cw, dh, dw))

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

if __name__ == '__main__':
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit()
    from my_module import solve
    Main()

Solution (Python):
from collections import deque


H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [input() for i in range(H)]

dist = [[10**9+7] * W for _ in range(H)]
Ch = Ch-1
Cw = Cw-1
Dh = Dh-1
Dw = Dw-1

queue = deque()
queue.append((Ch,Cw))
queue2 = deque()
dist[Ch][Cw] = 0

walk = [[0,1],[1,0],[0,-1],[-1,0]]
    
while len(queue) > 0:
    while len(queue) > 0:
        h, w = queue.popleft()
        d = dist[h][w]
        flag = 0
        for vh,vw in walk:
            nh = h + vh
            nw = w + vw
            if 0 <= nh and nh < H and 0 <= nw and nw < W:
                if S[nh][nw] == '.':
                    if dist[nh][nw] > d:
                        dist[nh][nw] = d
                        queue.append([nh,nw])
                else:
                        flag += 1
        if flag:
            queue2.append([h,w])
            
    while len(queue2) > 0:
        h, w = queue2.popleft()
        for vh in range(-2,3):
            for vw in range(-2,3):
                nh = h + vh
                nw = w + vw
                if 0 <= nh and nh < H and 0 <= nw and nw < W:
                    if S[nh][nw] == '.' and dist[nh][nw] == 10**9+7:
                        dist[nh][nw] = dist[h][w] + 1
                        queue.append([nh,nw])
                
if dist[Dh][Dw] != 10**9+7:
    print(dist[Dh][Dw])
else:
    print(-1)

Solution (Python):




import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict


MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

import numpy as np
from numba import i8, njit, u1, b1
from heapq import heappop, heappush

@njit(i8(b1[:,:], i8, i8, i8, i8), cache=True)
def solve(grid, ch, cw, dh, dw):
    h, w = grid.shape
    
    dist = np.full((h, w), INF, dtype=np.int64)
    dist[ch][cw] = 0

    que = [(0, ch, cw)]

    while que:
        cnt, y, x = heappop(que)

        if y == dh and x == dw:
            break

        for dy in range(-2, 3):
            for dx in range(-2, 3):
                if dx == 0 and dy == 0:
                    continue

                if abs(dx) == 2 or abs(dy) == 2 or (abs(dx) == 1 and abs(dy) == 1):
                    warp = 1
                else:
                    warp = 0

                nx, ny = x + dx, y + dy
                if nx < 0 or nx >= w or ny < 0 or ny >= h or grid[ny][nx]:
                    continue
                
                if dist[ny][nx] > cnt + warp:
                    dist[ny][nx] = cnt + warp
                    heappush(que, (cnt + warp, ny, nx))

    if dist[dh][dw] == INF:
        return - 1
    else:
        return dist[dh][dw]


def Main():
    H, W = read_ints()
    ch, cw = read_ints(); ch -= 1; cw -= 1
    dh, dw = read_ints(); dh -= 1; dw -= 1

    grid = np.array([[g == '
    
    print(solve(grid, ch, cw, dh, dw))

def cc_export(config):
    from numba.pycc import CC
    cc = CC('my_module')
    for func, signature in config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()

if __name__ == '__main__':
    Main()

Solution (Python):
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())
s=[list(input()) for _ in range(h)]

dy=[1, 0, -1, 0]
dx=[0, 1, 0 ,-1]
my=[-2, -2, -2, -2, -2, -1, -1, -1, -1, -1,  0,  0, 0, 0,  1,  1, 1, 1, 1,  2,  2,  2,  2,  2]
mx=[-2, -1,  0,  1,  2, -2, -1,  0,  1,  2, -2, -1, 1, 2, -2, -1, 0, 1, 2, -2, -1,  0,  1,  2]

from collections import deque

d=[[float("inf")]*w for _ in range(h)]
queue=deque()
queue.append((ch, cw))
d[ch][cw]=0

while queue:
    y,x=queue.popleft()

    for d_y, d_x in zip(dy, dx):
        new_y=y+d_y
        new_x=x+d_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]>d[y][x]:
            d[new_y][new_x]=d[y][x]
            queue.appendleft((new_y, new_x))

    for m_y, m_x in zip(my, mx):
        new_y=y+m_y
        new_x=x+m_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]==float("inf"):
            d[new_y][new_x]=d[y][x]+1
            queue.append((new_y, new_x))

print(-1 if d[dh][dw]==float("inf") else d[dh][dw])

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()
            if x == self.goal:
                break
            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):

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()
            if x == self.goal:
                break
            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())
CY, CX = map(lambda x: int(x)-1, input().split())
DY, DX = map(lambda x: int(x)-1, input().split())

gridgraph = [input() for _ in range(H)]
q = deque()
q.append([CY, CX])

adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]
INF = float("inf")
distant = [[INF]*W for _ in range(H)]
distant[CY][CX] = 0
visited = set()
while len(q):
    cy, cx = q.popleft()
    if (cy, cx) in visited:
        continue
    visited.add((cy, cx))
    for dy, dx in adjacent:
        ny, nx = cy+dy, cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if gridgraph[ny][nx] == "." and distant[ny][nx] > distant[cy][cx]:
            distant[ny][nx] = distant[cy][cx]
            q.appendleft([ny, nx])
    for i in range(-2, 3, 1):
        for j in range(-2, 3, 1):
            target_y, target_x = cy+i, cx+j
            if target_y < 0 or target_y >= H or target_x < 0 or target_x >= W:
                continue
            if gridgraph[target_y][target_x] == "." and distant[target_y][target_x] > distant[cy][cx]+1:
                distant[target_y][target_x] = distant[cy][cx]+1
                q.append([target_y, target_x])
if distant[DY][DX] == INF:
    print(-1)
else:
    print(distant[DY][DX])

Solution (Python):
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())
s=[list(input()) for _ in range(h)]

dy=[1, 0, -1, 0]
dx=[0, 1, 0 ,-1]
my=[-2, -2, -2, -2, -2, -1, -1, -1, -1, -1,  0,  0, 0, 0,  1,  1, 1, 1, 1,  2,  2,  2,  2,  2]
mx=[-2, -1,  0,  1,  2, -2, -1,  0,  1,  2, -2, -1, 1, 2, -2, -1, 0, 1, 2, -2, -1,  0,  1,  2]

from collections import deque

d=[[float("inf")]*w for _ in range(h)]
queue=deque()
queue.append((ch, cw))
d[ch][cw]=0

while queue:
    y,x=queue.pop()

    for d_y, d_x in zip(dy, dx):
        new_y=y+d_y
        new_x=x+d_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]>d[y][x]:
            d[new_y][new_x]=d[y][x]
            queue.append((new_y, new_x))

    for m_y, m_x in zip(my, mx):
        new_y=y+m_y
        new_x=x+m_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]==float("inf"):
            d[new_y][new_x]=d[y][x]+1
            queue.appendleft((new_y, new_x))

print(-1 if d[dh][dw]==float("inf") else d[dh][dw])

Solution (Python):
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()) 
grid = [['
for _ in range(h):
    grid.append(['
grid.append(['
grid.append(['

stack = [(sy, sx)]

move = [(-1, 0), (1, 0), (0, 1), (0, -1)]

visited = set()
ans = 0
while stack:
    edge = set()
    while stack:
        y, x = stack.pop()
        visited.add((y, x))
        if gy == y and gx == x:
            print(ans)
            quit()
        for my, mx in move:
            if (y+my, x+mx) in visited:
                continue
            if grid[y+my][x+mx] == '.':
                stack.append((y+my, x+mx))
            else:
                edge.add((y, x))
    ans += 1
    next_points = set()
    for y, x in edge:
        for dy in range(-2, 3):
            yy = y + dy
            for dx in range(-2, 3):
                xx = x + dx
                if grid[yy][xx] == '.' and not (yy, xx) in visited and not (yy, xx) in next_points:
                    next_points.add((yy, xx))
    stack = list(next_points)
print(-1)

Solution (Python):
from collections import*
INF=10**18
h,w=map(int,input().split())
sh,sw=map(int,input().split())
gh,gw=map(int,input().split())
s=[input() for _ in range(h)]
q=deque([(sh-1,sw-1,0)])
d=[[INF]*w for _ in range(h)]
dx=[1,0,-1,0]
dy=[0,-1,0,1]
wx=[-2,-1,0,1,2]
wy=[-2,-1,0,1,2]
while q:
  x,y,c=q.popleft()
  if d[x][y]!=INF:continue
  d[x][y]=c
  for i,j in zip(dx,dy):
    nx=x+i
    ny=y+j
    if not(0<=nx<h and 0<=ny<w):continue
    if s[nx][ny]=='.' and d[nx][ny]==INF:
      q.appendleft((nx,ny,c))
  for i in wx:
    nx=x+i
    if not(0<=nx<h):continue
    for j in wy:
      ny=y+j
      if not(0<=ny<w):continue
      if s[nx][ny]=='.' and d[nx][ny]==INF:
        q.append((nx,ny,c+1))
print(d[gh-1][gw-1]if d[gh-1][gw-1]!=INF else -1)

Solution (Python):
import sys
sys.setrecursionlimit(1<<20)
h,w=[int(x) for x in input().split()]
ch,cw=[int(x) for x in input().split()]
dh,dw=[int(x) for x in input().split()]
ch-=1
cw-=1
dh-=1
dw-=1

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

nxt=[[ch,cw,0]]

def rcl(y,x,now):
    
    if y==dh and x==dw:
        print(now)
        exit()
    
    if s[y][x]=='
        return
    
    s[y][x]='
    
    for i in range(4):
        yy,xx=-1,0
        if i==1:yy,xx=0,1
        if i==2:yy,xx=1,0
        if i==3:yy,xx=0,-1
        
        if y+yy<0 or h<=y+yy or x+xx<0 or w<=x+xx:
            continue
        if s[y+yy][x+xx]=='
            continue
        
        rcl(y+yy,x+xx,now)
    
    for i in range(-2,3):
        for j in range(-2,3):
            if i==0 and j==0:
                continue
            if y+i<0 or h<=y+i or x+j<0 or w<=x+j:
                continue
            if s[y+i][x+j]=='.':
                nxt.append([y+i,x+j,now+1])
                s[y+i][x+j]=now+1


idx=0
while idx<len(nxt):
    i=nxt[idx]
    idx+=1
    if i[0]==dh and i[1]==dw:
        print(i[2])
        exit()
    rcl(i[0],i[1],i[2])
print(-1)

Solution (Python):
from collections import deque

INF = float('inf')

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())
S = [input() for _ in range(H)]

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

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

Solution (Python):
h,w = list(map(int,input().split()))
sx, sy = list(map(int,input().split()))
gx, gy = list(map(int,input().split()))
maze = [list(input()) for _ in range(h)]
sx -= 1; sy -= 1; gx -= 1; gy -= 1

mx = [0,1,0,-1]
my = [1,0,-1,0]
mazemap = [[10**9]*w for _ in range(h)]
from collections import deque
q = deque()
nq = deque()
q.append([sx,sy,0])

while q or nq:
    x,y,z = q.popleft() if q else nq.popleft()
    if x == gx and y == gy:
        ans = z
        break
    for i in range(4):
        nx = x + mx[i]; ny = y + my[i]
        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "
            q.append([nx,ny,z])
            mazemap[nx][ny] = z
        for i in range(-2,3):
            for j in range(-2,3):
                nx = x+i; ny = y+j
                if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "
                    nq.append([nx,ny,z+1])
                    mazemap[nx][ny] = z+1
else:
    ans = -1

print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
CY, CX = map(lambda x: int(x)-1, input().split())
DY, DX = map(lambda x: int(x)-1, input().split())

gridgraph = [input() for _ in range(H)]
q = deque()
q.append([CY, CX])

adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]
INF = float("inf")
distant = [[INF]*W for _ in range(H)]
distant[CY][CX] = 0
while len(q):
    cy, cx = q.popleft()
    for dy, dx in adjacent:
        ny, nx = cy+dy, cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if gridgraph[ny][nx] == "." and distant[ny][nx] > distant[cy][cx]:
            distant[ny][nx] = distant[cy][cx]
            q.appendleft([ny, nx])
    for i in range(-2, 3, 1):
        for j in range(-2, 3, 1):
            target_y, target_x = cy+i, cx+j
            if target_y < 0 or target_y >= H or target_x < 0 or target_x >= W:
                continue
            if gridgraph[target_y][target_x] == "." and distant[target_y][target_x] > distant[cy][cx]+1:
                distant[target_y][target_x] = distant[cy][cx]+1
                q.append([target_y, target_x])
if distant[DY][DX] == INF:
    print(-1)
else:
    print(distant[DY][DX])