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

Solution (Python):

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

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

Solution (Python):
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] = ['
    
m = [['
ch+=2; cw+=2; dh+=2; dw+=2

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

    while que1!=[]:
        l1=len(que1)
        r1=0 

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

Solution (Python):

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


if __name__ == "__main__":
    main()

Solution (Python):
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 not (0 <= y < h and 0 <= x < w) or vis[y][x] or maze[y][x] == '
            continue
        vis[y][x] = True
        if (y, x) == goal:
            print(c)
            break
        for a, b in mw:
            q.appendleft((y + a, x + b, c))
        for a, b in mj:
            q.append((y + a, x + b, c + 1))
    else:
        print(-1)


if __name__ == '__main__':
    main()

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

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

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

Solution (Python):
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(1000000)

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

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

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

    
    
    
    
    
    
    
    
    
    
    
    
    

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