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
from itertools import product
h, w = map(int, input().split())
si, sj = map(lambda x: int(x)-1, input().split())
gi, gj = map(lambda x: int(x)-1, input().split())
fld = ''.join([input()for _ in range(h)])
INF = 10**18


def to_v(i, j):
    return i*w+j


n = h*w
start = to_v(si, sj)
goal = to_v(gi, gj)


def generate_v2(v):
    i, j = divmod(v, w)
    it = [-2, -1, 0, 1, 2]
    for di, dj in product(it, repeat=2):
        x, y = i+di, j+dj
        if x < 0 or h <= x or y < 0 or w <= y:
            continue
        if (di, dj) in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:
            d = 0
        else:
            d = 1
        yield d, x*w+y


def dijkstra(init_v):
    next_v = [(0, init_v)]
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        d, v = heapq.heappop(next_v)
        if dist[v] < d:
            continue
        for d, v2 in generate_v2(v):
            if fld[v2] == '
                continue
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            heapq.heappush(next_v, (dist[v2], v2))
    return dist


ans = dijkstra(start)[goal]
print(-1 if ans == INF else ans)

Solution (Python):
from itertools import product
from collections import deque
INF = 1e7
def main():
    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 = [["
    
    for i in range(2, H+2):
        tmp = input()
        for j in range(2, W+2):
            S[i][j] = tmp[j-2]
            
                

    dxdy = [(1,0), (-1,0), (0,1), (0,-1)]
    magic = list(product(range(-2, 3), repeat=2))
    magic.remove((0, 0))
    for to_remove in dxdy:
        magic.remove(to_remove)
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    def bfs(u,v):
        dist = [[INF] * (W+4) for _ in range(H+4)] 
        
        queue = deque()
        
        dist[u][v] = 0
        queue.append((u,v))
        while queue:
            p, q = queue.popleft()
            
            
            
            
            
            
            
            
            for dx, dy in dxdy:
                g = p+dx
                h = q+dy
                if S[g][h]=="." and dist[g][h] > dist[p][q]:
                    dist[g][h] = dist[p][q]
                    queue.appendleft((g,h))
            for dx, dy in magic:
                g = p+dx
                h = q+dy
                if S[g][h]=="." and dist[g][h] > dist[p][q]+1:
                    dist[g][h] = dist[p][q]+1
                    queue.append((g,h))
            
            
        return dist

    D = bfs(ch, cw)
    ans = D[dh][dw]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from itertools import product
from collections import deque
INF = 1e7
def main():
    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 = [["
    whites = [] 
    for i in range(2, H+2):
        tmp = input()
        for j in range(2, W+2):
            S[i][j] = tmp[j-2]
            if S[i][j] == ".":
                whites.append((i,j))

    dxdy = [(1,0), (-1,0), (0,1), (0,-1)]
    magic = list(product(range(-2, 3), repeat=2))
    magic.remove((0, 0))
    for to_remove in dxdy:
        magic.remove(to_remove)
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    def bfs(u,v):
        dist = [[INF] * (W+4) for _ in range(H+4)] 
        
        queue = deque()
        
        dist[u][v] = 0
        queue.append((u,v))
        while queue:
            p, q = queue.popleft()
            
            
            
            
            
            
            
            
            for dx, dy in dxdy:
                g = p+dx
                h = q+dy
                if S[g][h]=="." and dist[g][h] > dist[p][q]:
                    dist[g][h] = dist[p][q]
                    queue.appendleft((g,h))
            for dx, dy in magic:
                g = p+dx
                h = q+dy
                if S[g][h]=="." and dist[g][h] > dist[p][q]+1:
                    dist[g][h] = dist[p][q]+1
                    queue.append((g,h))
            
            
        return dist

    D = bfs(ch, cw)
    ans = D[dh][dw]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from itertools import product
from collections import deque
INF = 1e7
def main():
    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 = [["
    whites = [] 
    for i in range(2, H+2):
        tmp = input()
        for j in range(2, W+2):
            S[i][j] = tmp[j-2]
            if S[i][j] == ".":
                whites.append((i,j))

    dxdy = [(1,0), (-1,0), (0,1), (0,-1)]
    magic = list(product(range(-2, 3), repeat=2))
    magic.remove((0, 0))
    for to_remove in dxdy:
        magic.remove(to_remove)
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    def bfs(u,v):
        dist = [[INF] * (W+4) for _ in range(H+4)] 
        
        queue = deque()
        
        dist[u][v] = 0
        queue.append((u,v))
        while queue:
            p, q = queue.popleft()
            
            
            
            
            
            
            
            
            for dx, dy in dxdy:
                g = p+dx
                h = q+dy
                if S[g][h]=="." and dist[g][h] > dist[p][q]:
                    dist[g][h] = dist[p][q]
                    queue.appendleft((g,h))
            for dx, dy in magic:
                g = p+dx
                h = q+dy
                if S[g][h]=="." and dist[g][h] > dist[p][q]+1:
                    dist[g][h] = dist[p][q]+1
                    queue.append((g,h))
            
            
        return dist

    D = bfs(ch, cw)
    ans = D[dh][dw]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W = map(int, rl().split())
    ch, cw = map(lambda n: int(n) - 1, rl().split())
    dh, dw = map(lambda n: int(n) - 1, rl().split())
    S = [rl().rstrip() for _ in range(H)]
    
    INF = 10 ** 9
    costs = [[INF] * W for _ in range(H)]
    que = deque([(0, ch, cw)])
    while que:
        cost, cy, cx = que.popleft()
        if cy == dh and cx == dw:
            print(cost)
            return
        for dy, dx in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            ny, nx = cy + dy, cx + dx
            if 0 <= ny < H and 0 <= nx < W:
                if S[ny][nx] == '
                    continue
                if costs[ny][nx] <= cost:
                    continue
                que.appendleft((cost, ny, nx))
                costs[ny][nx] = cost
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny, nx = cy + dy, cx + dx
                if 0 <= ny < H and 0 <= nx < W:
                    if S[ny][nx] == '
                        continue
                    if costs[ny][nx] <= cost + 1:
                        continue
                    que.append((cost + 1, ny, nx))
                    costs[ny][nx] = cost + 1
    print(-1)


if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque
f_inf = float('inf')
H, W = map(int, input().split())
sh, sw = map(int, input().split())
sh, sw = sh-1, sw-1
eh, ew = map(int, input().split())
eh, ew = eh-1, ew-1
S = [list(input()) for _ in range(H)]
m = [[f_inf]*W for _ in range(H)]
m[sh][sw] = 0
que = deque([])
que.appendleft([sh,sw])
while que:
  h, w = que.popleft()
  for dh, dw in ((1,0), (-1,0), (0, 1), (0, -1)):
    next_h, next_w = h + dh, w + dw
    if 0 <= next_h < H and 0 <= next_w < W and S[next_h][next_w] == ".":
        if m[next_h][next_w] > m[h][w]:
          m[next_h][next_w] = m[h][w] 
          que.appendleft([next_h,next_w])
  for dh in range(-2, 3):
    for dw in range(-2, 3): 
      next_h, next_w = h + dh, w + dw
      if 0 <= next_h < H and 0 <= next_w < W and S[next_h][next_w] == ".":
        if m[next_h][next_w] > m[h][w] + 1: 
          m[next_h][next_w] = m[h][w] + 1 
          que.append([next_h, next_w]) 
print(m[eh][ew] if m[eh][ew] != f_inf else -1)

Solution (Python):


import collections

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['
checked=[[False]*(w+1) for _ in range(h+1)]
checked[sy][sx]=True
q=collections.deque()
q.append((sy,sx))
ans=0
while 1:
  cur_pos=[]
  while len(q)!=0:
    y,x=q.popleft()
    cur_pos.append((y,x))
    for dy,dx in [[-1,0],[1,0],[0,-1],[0,1]]:
      if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and checked[y+dy][x+dx]==False:
        checked[y+dy][x+dx]=True
        q.append((y+dy,x+dx))
  if checked[gy][gx]==True:
    print(ans)
    exit()
  if len(cur_pos)==0:
    print(-1)
    exit()
  ans+=1
  for y,x in cur_pos:
    for dy in range(-2,3):
      for dx in range(-2,3):
        if dy==0 and dx==0:
          continue
        if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and checked[y+dy][x+dx]==False:
          checked[y+dy][x+dx]=True
          q.append((y+dy,x+dx))

Solution (Python):
import sys
from io import StringIO
import unittest
import os
from collections import deque


sys.setrecursionlimit(999999999)


class UnionFind:
    def __init__(self, n):
        """
        コンストラクタ
        :要素数 n:
        """
        self.n = n
        
        
        
        self.parents = [-1] * n

    def getroot(self, x):
        """
        データが属するグループのID(と考えて良いはず)を取得する。
        :調査するグループ x:
        """
        
        if self.parents[x] < 0:
            return x
        else:
            
            
            self.parents[x] = self.getroot(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        2つのデータが属するグループを結合する。
        :結合するデータ(1つ目) x:
        :結合するデータ(2つ目) y:
        """
        
        x = self.getroot(x)
        y = self.getroot(y)
        if x == y:
            return

        
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        """
        指定したグループに属するデータの数を返す。
        :調査グループ x:
        """
        
        return -self.parents[self.getroot(x)]

    def is_same(self, x, y):
        return self.getroot(x) == self.getroot(y)

    def members(self, x):
        """
        指定したグループに属するデータの一覧を返す。size()と比較して速度が圧倒的に遅いので注意。
        :調査グループ x:
        """
        root = self.getroot(x)
        return [i for i in range(self.n) if self.getroot(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())





class youk_maze:
    __maze = []
    __wall_str = ""
    __road_str = ""
    __road_s = []  
    __wall_s = []  
    __arrived_s = []  
    __not_arrived_val = -1  

    def __init__(self, maze: [], can_move_out: bool = False, wall_str: str = "
        """
        コンストラクタ
        :maze 迷路の情報を保持する2次元配列
        :can_move_out 迷路の外側に出れるか(True:出れる、False:出れない)
        """

        if len(maze) == 0:
            raise ValueError("迷路の情報が設定されていない = len()が0")

        
        
        
        self.__wall_str = wall_str
        self.__road_str = road_str

        
        
        
        
        
        frame = road_str if can_move_out else wall_str
        
        self.__maze = [[frame] + [frame for _ in range(len(list(maze[0])))] + [frame]]
        
        for line in maze:
            self.__maze.append([frame] + line + [frame])
        
        self.__maze.append([frame] + [frame for _ in range(len(maze[0]))] + [frame])

        
        
        
        self.__road_s = []
        self.__wall_s = []
        for i in range(len(self.__maze)):
            for j in range(len(self.__maze[0])):
                
                if self.__maze[i][j] == self.__wall_str:
                    self.__wall_s.append([i, j])
                elif self.__maze[i][j] == self.__road_str:
                    self.__road_s.append([i, j])

        
        
        
        self.reset_arrived()

    def get_road_list(self):
        """
        座標の一覧を取得(道)
        """
        return self.__road_s

    def get_wall_list(self):
        """
        座標の一覧を取得(壁)
        """
        return self.__wall_s

    def get_maze(self):
        """
        迷路情報を返す
        """
        return self.__maze

    def is_arrived(self, cell: []):
        """
        指定された経路の到達情報を返す。(-1：未到達)
        """
        return self.__arrived_s[cell[0], cell[1]]

    def can_moved(self, cell: []) -> bool:
        """
        指定された経路に移動できるかを返す。(True:移動可能、False:移動不可)
        """
        
        if not 0 <= cell[0] < len(self.__maze) or not 0 <= cell[1] < len(self.__maze[0]):
            return False

        
        if self.__maze[cell[0]][cell[1]] == self.__wall_str:
            return False

        
        
        

        return True

    def set_arrived(self, cell: [], val):
        """
        指定された経路に到達情報を設定する。
        """
        self.__arrived_s[cell[0]][cell[1]] = val

    def reset_arrived(self):
        """
        経路の到達情報を初期化する。(DFSを再度行う場合などに使用)
        """
        self.__arrived_s = [[self.__not_arrived_val for i in range(len(self.__maze[0]))] for j in
                            range(len(self.__maze))]

    def get1dpoint(self, cell) -> int:
        """
        座標情報を1次元に変換したものを返す。対象を1次元で管理する処理との連携に使用する。(例：UnionFind)
        """
        
        return cell[0] * len(self.__maze[0]) + cell[1]

    def getcellcount(self) -> int:
        """
        座標数を返す(囲み枠を考慮した座標数を返す)
        """
        
        return len(self.__maze) * len(self.__maze[0])

    def debugmazemap(self) -> str:
        """
        ※デバック用変数※
        迷路をテキスト形式で返す(タブ区切り)
        """
        ans = ""
        for i in range(len(self.__maze)):
            ans += "\t".join(self.__maze[i]) + "\n"
        return ans

    def debugmazearrived(self) -> str:
        """
        ※デバック用変数※
        到達リストをテキスト形式で返す(タブ区切り)
        """
        ans = ""
        for i in range(len(self.__maze)):
            ans += "\t".join(map(str, self.__arrived_s[i])) + "\n"
        return ans

    def debugmazeoriginval(self, info_list: [] = []) -> str:
        """
        ※デバック用変数※
        迷路の各座標と受け取った一次元配列の情報を紐づけして返す(タブ区切り)
        """
        if len(info_list) == 0:
            info_list = self.__arrived_s

        ans = ""
        for i in range(len(self.__maze)):
            line = ""
            for j in range(len(self.__maze[0])):
                point = self.get1dpoint([i, j])
                line += str(info_list[point]) + "\t"
            ans += line + "\n"
        return ans



def resolve(test_def_name=""):
    global h
    h, w = map(int, input().split())

    start = list(map(int, input().split()))
    gorl = list(map(int, input().split()))

    maze = youk_maze([list(input()) for i in range(h)])

    h += 1
    w += 1
    
    start_list = maze.get_road_list()

    
    uf = UnionFind(maze.getcellcount())

    que = deque()
    que.extend(start_list)

    
    
    while len(que) is not 0:
        now = que.pop()
        now_point = maze.get1dpoint(now)

        
        for move_h, move_w in [(1, 0), (0, 1), (0, -1), (-1, 0)]:
            target = [now[0] + move_h, now[1] + move_w]
            if not maze.can_moved(target):
                continue
            maze.set_arrived(target, 1)
            target_point = maze.get1dpoint(target)
            uf.union(now_point, target_point)

    
    move_target_list = [set() for a in range(maze.getcellcount())]

    
    maze.reset_arrived()  
    que.extend(start_list)
    while len(que) is not 0:
        now = que.pop()
        now_root = uf.getroot(maze.get1dpoint(now))

        
        for i, j in [(-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)]:
            
            target = [now[0] + i, now[1] + j]
            if not maze.can_moved(target):
                continue

            
            target_root = uf.getroot(maze.get1dpoint(target))
            if not uf.is_same(now_root, target_root):
                move_target_list[now_root].add(target_root)

    
    start_erea = uf.getroot(maze.get1dpoint(start))

    
    area_list = [-1 for a in range(maze.getcellcount())]
    area_list[start_erea] = 0

    que.append(start_erea)
    while len(que) is not 0:
        now = que.pop()

        
        for move_target in move_target_list[now]:

            
            if not area_list[move_target] == -1:
                continue

            
            que.appendleft(move_target)

            
            area_list[move_target] = area_list[now] + 1

    gorl_area = uf.getroot(maze.get1dpoint(gorl))
    print(area_list[gorl_area])

    


class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4 4
1 1
4 4
..
..
.
.
        output = """1"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """4 4
1 4
4 1
.


.
        output = """-1"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """4 4
2 2
3 3
....
....
....
...."""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """4 5
1 2
2 5




        output = """2"""
        self.assertIO(test_input, output)

    
    def test_original(self):
        test_input = """4 4
2 2
3 3
....
..
.
...."""
        output = """0"""
        self.assertIO(test_input, output)

    
    def test_origina2(self):
        test_input = """4 4
2 2
3 3
....
..
.
...."""
        output = """0"""
        self.assertIO(test_input, output)

    
    def test_origina3(self):
        test_input = """4 4
2 2
3 3
....
..

...."""
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_origina4(self):
        test_input = """4 4
1 1
3 3
.
..

...."""
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_origina5(self):
        test_input = """4 4
1 1
4 4
.


...."""
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_origina6(self):
        test_input = """4 4
1 1
4 4
.


...."""
        output = """2"""
        self.assertIO(test_input, output)

    
    def test_origina7(self):
        test_input = """1 4
1 1
1 4
...."""
        output = """0"""
        self.assertIO(test_input, output)

    
    def test_origina8(self):
        test_input = """1 4
1 1
1 4
.
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_origina9(self):
        test_input = """1 4
1 4
1 1
..
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_origina10(self):
        test_input = """4 1
4 1
1 1
.
.

.
"""
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_origina11(self):
        test_input = """4 1
1 1
4 1
.
.

.
"""
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_original12(self):
        test_input = """6 6
1 1
6 6
......
......
......
......
......
......"""
        output = """0"""
        self.assertIO(test_input, output)

    
    def test_original13(self):
        test_input = """6 6
1 1
6 6
......

......
......
......
......"""
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_original14(self):
        test_input = """6 6
1 1
6 6
......


......
......
......"""
        output = """-1"""
        self.assertIO(test_input, output)

    
    def test_original15(self):
        test_input = """6 6
1 1
6 6
......

.
.

......"""
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_original16(self):
        test_input = """6 6
1 1
6 1
......

.
.

....
        output = """2"""
        self.assertIO(test_input, output)

    
    def test_original17(self):
        test_input = """6 6
3 3
6 1
......

.
.

....
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_original17(self):
        test_input = """6 6
1 1
4 4
.
.
.
.
.
.
        output = """1"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
from collections import deque
from sys import stdin

def bfs():
    readline=stdin.readline
    h,w=map(int,readline().split())
    sy,sx=map(int,readline().split())
    gy,gx=map(int,readline().split())
    sy-=1;sx-=1;gy-=1;gx-=1
    s=[list(readline()) for _ in range(h)]
    dict={".":10000000,"
    s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]
    s[sy][sx]=0
    que=deque([[sy,sx]])
    temp=[i for i in range(-2,3)]
    while que:
        y,x=que.popleft()
        s1=s[y][x]
        for i in temp:
            nexty=y+i
            if 0<=nexty<h:
                s2=s[nexty]
                for j in temp:
                    nextx=x+j
                    if 0<=nextx<w and s2[nextx]>=0:
                        dist=s2[nextx]
                        if i*i+j*j<=1 and dist>s1:
                            s[nexty][nextx]=s1
                            que.appendleft([nexty,nextx])
                        elif dist>s1+1:
                            s[nexty][nextx]=s1+1
                            que.append([nexty,nextx])

    if s[gy][gx]==10000000:
        print(-1)
    else:
        print(s[gy][gx])
bfs()

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

class RadixHeap:
    __slots__ = ["v", "last", "size"]

    def __init__(self, C=1 << 31):
        self.last = 0
        self.size = 0
        self.v = [[] for _ in range(C.bit_length()+1)]

    def push(self, key, val):
        self.size += 1
        self.v[(key ^ self.last).bit_length()].append((key, val))

    def pop(self):
        v = self.v
        if not v[0]:
            i = 1
            while not v[i]:
                i += 1
            vi = v[i]
            new_last, _ = min(vi)
            for key, val in vi:
                v[(key ^ new_last).bit_length()].append((key, val))
            self.last = new_last
            vi.clear()
        self.size -= 1
        return v[0].pop()

    def __len__(self): return self.size

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

INF = 10**10
D = [[INF]*W for _ in [0]*H]

q = RadixHeap()
q.push(0, Ch*W+Cw)

while q:
    d, ij = q.pop()
    i, j = divmod(ij, W)

    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            I = i+di
            J = j+dj
            if 0 <= I < H and 0 <= J < W and S[I][J] == '.':
                if abs(di)+abs(dj) == 1:
                    if D[I][J] <= d:
                        continue
                    D[I][J] = d
                    q.push(d, I*W+J)
                else:
                    if D[I][J] <= d+1:
                        continue
                    D[I][J] = d+1
                    q.push(d+1, I*W+J)

ans = D[Dh][Dw]
print(ans if ans < INF else -1)

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque

h,w = map(int,readline().split())
ch,cw = map(int,readline().split())
dh,dw = map(int,readline().split())
s = read().split()

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

wall = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if(s[i][j] == '
            wall[i][j] = 1

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

while(d):
    ci,xi,yi = d.popleft()
    if(cost[xi][yi] > ci):
        continue

    for dx in range(-2,3):
        xj = xi+dx
        if(xj<0)|(xj>=h):
            continue
        for dy in range(-2,3):
            yj = yi+dy
            
            if(yj<0)|(yj>=w):
                continue
            if(xi==xj)&(yi==yj):
                continue
            if(wall[xj][yj]==1):
                continue
            if(abs(xi-xj)+abs(yi-yj)==1):
                if(cost[xj][yj] > ci):
                    cost[xj][yj] = ci
                    d.appendleft((ci,xj,yj))
            else:
                if(cost[xj][yj] > ci+1):
                    cost[xj][yj] = ci+1
                    d.append((ci+1,xj,yj))

if(cost[dh][dw] == inf):
    print(-1)
else:
    print(cost[dh][dw])

Solution (Python):
H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())

sh += 1
sw += 1
gh += 1
gw += 1

S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [[float('inf')]*(W+4) for _ in range(H+4)]
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from collections import deque
d = deque()

d.append((sh,sw,0))

while len(d)>0:
  h,w,cnt = d.popleft()
  if visited[h][w]<=cnt:
    continue
  visited[h][w] = cnt
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    if S[h1][w1]=='.':
      if visited[h1][w1]>cnt:
        d.appendleft((h1,w1,cnt))
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    if S[h2][w2]=='.':
      if visited[h2][w2]>cnt+1:
        d.append((h2,w2,cnt+1))
ans = visited[gh][gw] if visited[gh][gw]<float('inf') else -1
print(ans)

Solution (Python):
H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())

sh += 1
sw += 1
gh += 1
gw += 1
S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [[float('inf')]*(W+4) for _ in range(H+4)]
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from collections import deque

d = deque()
visited[sh][sw] = 0
d.append((sh,sw))
ans = float('inf')
while len(d)>0:
  h,w = d.popleft()
  cnt = visited[h][w]
  if ans<cnt:
    continue
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    if (h1,w1)==(gh,gw):
      ans = min(ans,cnt)
    if S[h1][w1]=='.':
      if visited[h1][w1]>cnt:
        visited[h1][w1]=cnt
        d.appendleft((h1,w1))
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    if (h2,w2)==(gh,gw):
      ans = min(ans,cnt+1)
    if S[h2][w2]=='.':
      if visited[h2][w2]>cnt+1:
        visited[h2][w2]=cnt+1
        d.append((h2,w2))
if ans==float('inf'):
  ans = -1
print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

dd = [(1,0),(0,1),(-1,0),(0,-1)]
h,w = inpl()
cy,cx = inpl()
gy,gx = inpl()
cy,cx,gy,gx = cy-1,cx-1,gy-1,gx-1
s = [input() for _ in range(h)]
res = [[INF] * w for _ in range(h)]
res[cy][cx] = 0
seen = set()
q = deque([(cy,cx)])
while q:
    oy,ox = q.popleft()
    if (oy,ox) in seen: continue
    seen.add((oy,ox))
    for dy,dx in dd:
        ny = oy+dy; nx = ox+dx
        if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == '.':
            if res[ny][nx] > res[oy][ox]:
                res[ny][nx] = res[oy][ox]
                q.appendleft((ny,nx))
        for dy in range(-2,3):
            for dx in range(-2,3):
                ny = oy+dy; nx = ox+dx
                if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == '.':
                    if res[ny][nx] > res[oy][ox] + 1:
                        res[ny][nx] = res[oy][ox] + 1
                        q.append((ny,nx))
ans = res[gy][gx]
print(-1 if ans  == INF else ans)

Solution (Python):
H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())

sh += 1
sw += 1
gh += 1
gw += 1
s = sh*(W+4)+sw
g = gh*(W+4)+gw
S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [10**7]*((W+4)*(H+4))
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from collections import deque

d = deque()
visited[s] = 0
d.append(s)
ans = 10**8
while len(d)>0:
  a = d.popleft()
  h,w = divmod(a,W+4)
  cnt = visited[a]
  if ans<=cnt:
    continue
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    a1 = h1*(W+4)+w1
    if (h1,w1)==(gh,gw):
      ans = min(ans,cnt)
    if S[h1][w1]=='.':
      if visited[a1]>cnt:
        visited[a1]=cnt
        d.appendleft(a1)
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    a2 = h2*(W+4)+w2
    if (h2,w2)==(gh,gw):
      ans = min(ans,cnt+1)
    if S[h2][w2]=='.':
      if visited[a2]>cnt+1:
        visited[a2]=cnt+1
        d.append(a2)
if ans==10**8:
  ans = -1
print(ans)