Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Runtime Error

Solution code:
import sys, math, heapq



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    deque = []
    dists = [ [inf for _ in range(W) ] for _ in range(H)]

    heapq.heappush(deque, [0, start[1], start[0], 0]) # [dist, x, y, neighbour_only]
    # neighbour_only: 0 -> T, 1-4 -> L, R, D, U, 5-> All
    dists[start[0]][start[1]] = 0
    while( len(deque)>0 ):
        dist_pos = heapq.heappop(deque)

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        if(dist_pos[3] == 0):
            for dx, dy, i in ( (-1, 0, 1), (1, 0, 2), (0, -1, 3), (0, 1, 4) ):
                if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                    continue
                if(Maps[y+dy][x+dx]=="#"):
                    Flag = i
                    N_Flag += 1
                    continue

                next = [x+ dx, y+ dy]
                #print([x, y], next)
                if(dists[next[1] ][next[0] ] > dists[y][x]):
                    dists[next[1] ][next[0] ] = dists[y][x]
                    heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1], 0])
            if(N_Flag >1):
                heapq.heappush(deque, [ dists[y][x], x, y, 5 ])
            elif(N_Flag > 0):
                heapq.heappush(deque, [ dists[y][x], x, y, Flag ])
        elif(dist_pos[3] == 5):
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1], 0])

        else:
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(dist_pos[4] == 3):
                dy_min = 1
            elif(dist_pos[3] == 2):
                dy_max = 0
            elif(dist_pos[2] == 1):
                dx_min = 1
            else:
                dx_max = 0
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1], 0])




    #print(dists)
    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)
    else:
        print(dists[goal[0]][goal[1]])

Submission status: Runtime Error

Solution code:
import sys
def main():
    movex = (1, 0, -1, 0)
    movey = (0, -1, 0, 1)
    warpx = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpy = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)
    def dfs1(cur_coor):
        flag = False
        nexts = []
        for i1 in range(4):
            nexty = cur_coor[0] + movey[i1]
            nextx = cur_coor[1] + movex[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(maze[cur_coor[0]][cur_coor[1]])
                sys.exit()
            elif nextg == '.':
                maze[nexty][nextx] = maze[cur_coor[0]][cur_coor[1]]
                nexts.append((nexty, nextx))
            elif nextg == '#':
                flag = True
            if type(nextg) == int:
                if nextg < maze[cur_coor[0]][cur_coor[1]]:
                    maze[cur_coor[0]][cur_coor[1]] = nextg
                elif nextg > maze[cur_coor[0]][cur_coor[1]]:
                    maze[nexty][nextx] = maze[cur_coor[0]][cur_coor[1]]
                    nexts.append((nexty, nextx))
        for ne in nexts:
            dfs1(ne)
        if flag:
            dfs2(cur_coor)

    def dfs2(cur_coor):
        """
        for i1 in range(4):
            nexty = cur_coor[0] + movey[i1]
            nextx = cur_coor[1] + movex[i1]
            nextg = maze[nexty][nextx]
            if type(nextg) == int:
                if nextg < maze[cur_coor[0]][cur_coor[1]]:
                    maze[cur_coor[0]][cur_coor[1]] = nextg
        """
        for j1 in range(20):
            nexty = cur_coor[0] + warpy[j1]
            nextx = cur_coor[1] + warpx[j1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(maze[cur_coor[0]][cur_coor[1]] + 1)
                sys.exit()
            elif nextg == '#':
                pass
            elif nextg == '.':
                maze[nexty][nextx] = maze[cur_coor[0]][cur_coor[1]] + 1
                dfs1((nexty, nextx))
            elif maze[nexty][nextx] > maze[cur_coor[0]][cur_coor[1]] + 1:
                maze[nexty][nextx] = maze[cur_coor[0]][cur_coor[1]] + 1
                dfs1((nexty, nextx))

    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
    dummy = ['#'] * (w + 4)
    maze = list()
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'

    dfs1((ch, cw))
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
from numba import njit, b1, i4, i8, f8



h, w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
mp = [None]+[[None]+[c for c in input()] for _ in range(h)]

d = deque([(ch,cw)])
mp[ch][cw]=0

cost = 0

def mass11(_h, _w):
    l = []
    for i,j in [(-1,0),(1,0),(0,1),(0,-1)]:
        side_h, side_w = _h+i, _w+j
        if side_h>0 and side_h<=h and side_w>0 and side_w<=w:
            l.append((side_h, side_w))
    return l 

def mass55(_h, _w):
    l = []
    for i in range(5):
        for j in range(5):
            side_h, side_w = _h+i-2, _w+j-2
            if side_h>0 and side_h<=h and side_w>0 and side_w<=w:
                l.append((side_h, side_w))
    return l 

@njit((b1[:, :], i8, i8, i8, i8), cache=True)
def main():
    while not len(d) == 0:
        _h, _w = d.popleft()
        center_point = mp[_h][_w]
        # print(_h, _w)
        for side_h, side_w in mass11(_h, _w):
            side = mp[side_h][side_w]
            # print('side',side_h, side_w,side)
            if not side == '#' and not side == mp[_h][_w]:
                mp[side_h][side_w]=center_point
                d.appendleft((side_h, side_w))
        for side_h, side_w in mass55(_h, _w):
            if mp[side_h][side_w] == '.':
                mp[side_h][side_w]=center_point+1
                d.append((side_h, side_w))

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


main()

Submission status: Runtime Error

Solution code:
import sys
from io import StringIO
import unittest
import os
from collections import deque
import itertools

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


class UnionFind:
    def __init__(self, n):
        """
        コンストラクタ
        :要素数 n:
        """
        self.n = n
        # 添字x: 値yとすると・・
        #   root以外の場合： 要素xは集合yに所属する。
        #   rootの場合　　　： 集合xの要素数はy個である。(負数で保持する)
        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:
        """
        # 添え字[root]には、要素数が負数で格納されている。そのため、取得する際は-反転する。
        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())


h = 0


def getpoint(point):
    global h
    ans = 0
    return (h - 1) * point[0] + point[1]


# 迷路(2次元)を扱うクラス
# ※3次元の迷路を扱いたい場合、このクラスのインスタンスを複数生成すれば良いはず。
class youk_maze:
    __maze = []
    __wall_str = ""
    __road_str = ""
    __road_s = []  # 座標の一覧(道)
    __wall_s = []  # 座標の一覧(壁)
    __arrived_s = []  # 到達情報(初期値-1；未到達)
    __not_arrived_val = -1  # 到達情報_未到達の初期値

    def __init__(self, maze: [], can_move_out: bool = False, wall_str: str = "#", road_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

        # -----------------
        # 迷路の作成(迷路を道or陰で囲む)
        # 目的1:　Atcoderでは座標が「1」始まりで与えられるため、迷路も開始添え字を1にして処理を明瞭にする。
        # 目的2: 迷路の外に出れるパターンの場合、迷路を道で囲む。
        # -----------------
        frame = road_str if can_move_out else wall_str
        # 1行目
        self.__maze = [[frame] + [frame for _ in range(len(list(maze[0])))] + [frame]]
        # 2~最終行手前
        for line in maze:
            self.__maze.append([frame] + line + [frame])
        # 最終行
        self.__maze.append([frame] + [frame for _ in range(len(maze[0]))] + [frame])

        # -----------------
        # 道と壁の一覧をリストにまとめておく
        # -----------------
        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

        # 処理済みなら何もしない(移動したければ編集するといい)
        if self.__arrived_s[cell[0]][cell[1]] != self.__not_arrived_val:
            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 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()

    # 集合の分類(-1：未調査)
    ed_list = [[-1 for i in range(w)] for j in range(h)]

    # UnionFindにて集合を明確にする。
    uf = UnionFind(h * w)

    que = deque()
    que.extend(start_list)

    # スタート地点の候補数だけ、BFSを行う(今回の問題固有で必要なループ)
    # BFS開始
    while len(que) is not 0:
        now = que.pop()

        # 各方向に集合が存在するか確認
        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)
            uf.union(getpoint(now), getpoint(target))

    # 探索処理
    move_target_list = [[] for i in range(h * w)]

    # BFS開始
    maze.reset_arrived()  # 到達情報を初期化(これをしておかないと、以下のBFSが動かない)
    que.extend(start_list)
    while len(que) is not 0:
        now = que.pop()

        # 各方向に集合が存在するか確認
        for i, j in [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),
                     (1, -2), (1, -1), (1, 0), (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

            # ワープ前後の座標のエリアが異なる場合のみ、リストに追加。
            if not uf.is_same(getpoint(now), getpoint(target)):
                move_target_list[uf.getroot(getpoint(now))].append(uf.getroot(getpoint(target)))

    moved_list = [-1 for a in range(1500000)]

    # リストから重複を排除。
    move_target_list = [set(a) for a in move_target_list]

    # スタート地点のエリアからBFSを実施。
    que.append(uf.getroot(getpoint(start)))
    while len(que) is not 0:
        now = que.pop()

        for aaa in move_target_list[now]:

            # 距離が設定済みなら何もしない
            if not moved_list[aaa] == -1:
                continue

            # キューに追加
            que.appendleft(aaa)

            # 最短距離を設定
            moved_list[aaa] = moved_list[now] + 1

    if uf.is_same(getpoint(start), getpoint(gorl)):
        print(0)
        return

    if moved_list[uf.getroot(getpoint(gorl))] == -1:
        print(-1)
        return

    print(moved_list[uf.getroot(getpoint(gorl))] + 1)

    # テストクラス


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


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, shortest_path


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Ch, Cw = Ch-1, Cw-1
    addr_c = Ch*W+Cw
    Dh, Dw = map(int, input().split())
    Dh, Dw = Dh-1, Dw-1
    addr_d = Dh*W+Dw
    #print(addr_c, addr_d)
    g = np.full((H*W, H*W), np.inf)
    S = []  #S[w][h]でアクセス すなわちy,x
    for _ in range(W):
        S.append([True if x=='.' else False for x in input()])
    
    for x, y in itertools.product(range(H), range(W)):
        addr = x*W + y
        if not S[y][x]:
            continue
        for xx, yy in [(x,y+1), (x, y-1), (x+1, y), (x-1, y)]:
            if xx<0 or yy<0 or xx>=H or yy>=W:
                continue
            if S[yy][xx]:
                #print(f"{x},{y} -> {xx}, {yy}")
                addr2 = xx*W + yy
                g[addr, addr2] = 0
                g[addr2, addr] = 0
        for xx, yy in [(x,y+2), (x, y-2), (x+2, y), (x-2, y)]:
            if xx<0 or yy<0 or xx>=H or yy>=W:
                continue
            if S[yy][xx]:
                #print(f"{x},{y} => {xx}, {yy}")
                addr2 = xx*W + yy
                g[addr, addr2] = 1
                g[addr2, addr] = 1
    #print(g)
    #G2_masked = np.ma.masked_invalid(g)
    #print(G2_masked)
    #print(type(G2_masked))
    G2_sparse = csgraph_from_dense(g, null_value=np.inf)
    #print(G2_sparse)
    #print(type(G2_sparse))
    path = shortest_path(G2_sparse, indices=addr_c)
    if path[addr_d] != np.inf:
        print(int(path[addr_d]))
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
#import sys
#sys.setrecursionlimit(6000)

def bfs01(start_h, start_w, S, H, W):
    path = deque()
    path.append((start_h, start_w, 0))  #x, y, cost
    cost0 = set()
    cost1 = set()
    scores = [[10**18]*(H+1)]*(W+1)
    scores[start_w][start_h] = 0
    #BFS
    while path:
        x, y, cost = path.pop()
        if (x,y) in cost0:
            continue
        elif (x,y) in cost1 and cost==1:
            continue
        #print((x, y, cost))
        if cost==0:
            cost0.add((x,y))
        elif cost==1:
            cost1.add((x,y))
        else:
            assert False
        for xx, yy in [(x,y+1), (x, y-1), (x+1, y), (x-1, y)]:
            if xx<0 or yy<0 or xx>H or yy>W:
                continue
            if scores[yy][xx] <= scores[y][x]:
                continue
            #print(f"xx, yy={xx},{yy}")
            if S[yy][xx]:
                path.append((xx, yy,0))
                scores[yy][xx] = scores[y][x]
        for xx, yy in [(x,y+2), (x, y-2), (x+2, y), (x-2, y)]:
            if xx<0 or yy<0 or xx>H or yy>W:
                continue
            if scores[yy][xx] <= scores[y][x] + 1:
                continue
            #print(f"xx, yy={xx},{yy}")
            if S[yy][xx]:
                path.appendleft((xx, yy,1))
                scores[yy][xx] = scores[y][x] + 1
    return scores

def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [[False]*(W+1)]  #S[w][h]でアクセス すなわちy,x
    for _ in range(W):
        S.append([False] + [True if x=='.' else False for x in input()])
    
    scores = bfs01(Ch, Cw, S, H, W)
    if scores[Dw][Dh] == 10**18:
        print(-1)
    else:
        print(scores[Dw][Dh])




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
from sys import exit

h,w=map(int,input().split())
sh,sw=map(lambda s: int(s)-1,input().split())
gh,gw=map(lambda s: int(s)-1,input().split())
s = [input() for _ in range(h)]
d = [[h*w] * w for _ in range(h)]
q = deque()
d[sh][sw] = 0
q.append((sw, sh))
while len(q):
  p = q.popleft()
  if p[2] != d[p[1]][p[0]]:
    continue
  if p[0] == gw and p[1] == gh:
    print(d[gh][gw])
    exit(0)
  for dx in range(-2, 3):
    nx = p[0] + dx
    if nx < 0 or w <= nx:
      continue
    for dy in range(-2, 3):
      ny = p[1] + dy
      c = 0 if abs(dx) + abs(dy) == 1 else 1
      if dx == dy == 0 or ny < 0 or h <= ny or s[ny][nx] == '#' or d[ny][nx] <= d[p[1]][p[0]] + c:
        continue
      d[ny][nx] = d[p[1]][p[0]] + c
      np = (nx, ny, d[ny][nx])
      if c:
        q.append(np)
      else:
        q.appendleft(np)
print(-1)

Submission status: Runtime Error

Solution code:
H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[10**8]*W for i in range(H)]
DD=[[-1]*W for i in range(H)]
dy=[-1,1,0,0]
dx=[0,0,1,-1,]
ey=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ex=[0,1,2,-1,-2,1,2,-1,-2,2,-2,1,2,-1,-2,0,1,2,-1,-2]
for h in range(H):
  for w in range(W):
    if A[h][w]=='#':
      D[h][w]=10**5
from collections import deque
import sys
sys.setrecursionlimit(10**7) 
def bfs(y,x):
  q=deque()
  q.append((y,x))
  
  while len(q):
    y,x=q.popleft()
    cnt=0
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W:
        if A[ny][nx]=='.' and D[y][x]<D[ny][nx]:
          q.appendleft((ny,nx))
          D[ny][nx]=D[y][x]
          DD[ny][nx]=1

    for i in range(20):
      my=y+ey[i]
      mx=x+ex[i]
      if 0<=my<H and 0<=mx<W:
        if A[my][mx]=='.' and D[my][mx]==10**8 and DD[my][my]==-1:
          q.append((my,mx))
          D[my][mx]=D[y][x]+1
            
D[Ch-1][Cw-1]=0
bfs(Ch-1,Cw-1)
if D[Dh-1][Dw-1]==10**8:
  print(-1)
else:
  print(D[Dh-1][Dw-1])

Submission status: Runtime Error

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10**9)

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

G = []
for i in range(h):
    G.append(list(input()))

queue = deque([(ch-1, cw-1)])
S = [[float("inf")]*w for _ in range(h)]
S[ch][cw] = 0

while queue:
    y, x = queue.popleft()
    dx_dy = ((1,0),(0,1),(-1,0),(0,-1))
    ans = S[y][x]

    if (y, x) == (dy, dx):
            S[y][x] = ans
            break

    for j, i in dx_dy:
        if 0 <= x+i < w and 0 <= y+j < h:
            if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                S[y+j][x+i] = ans
                queue.appendleft((y+j, x+i))

    ans += 1
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i != 0 and j != 0:
                if 0 <= x+i < w and 0 <= y+j < h:
                    if S[y+j][x+i] > ans and G[y+j][x+i] == ".":
                        S[y+j][x+i] = ans
                        queue.append((y+j, x+i))


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

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch = ch - 1
cw = cw - 1
dh = dh - 1
dw = dw - 1

S = []
nextIndex = 0
requiredWarps=[]
indexes = [[-1 for j in range(H)] for i in range(W)]
warpjudgeindexes=[[-1 for j in range(H)] for i in range(W)]
for i in range(H):
    S.append(input())

def DFS(i,j):
    for a in range(4):
        if a == 0:
            if i+1<H and indexes[i+1][j] == -1 and S[i+1][j]==".":
                indexes[i + 1][j] = indexes[i][j]
                DFS(i+1,j)
        elif a == 1:
            if i>0 and indexes[i-1][j] == -1 and S[i-1][j]==".":
                indexes[i -1][j] = indexes[i][j]
                DFS(i-1,j)
                
        elif a == 2:
            if j+1<W and indexes[i][j+1] == -1 and S[i][j+1]==".":
                indexes[i][j+1] = indexes[i][j]
                DFS(i,j+1)
            
        elif a == 3:
            if j>0 and indexes[i][j-1] == -1 and S[i][j-1]==".":
                indexes[i][j-1] = indexes[i][j]
                DFS(i, j - 1)

def WarpDFS(i, j):
    warp(i,j)
    for a in range(4):
        if a == 0:
            if i+1<H and warpjudgeindexes[i+1][j] == -1 and S[i+1][j]==".":
                warpjudgeindexes[i + 1][j] = warpjudgeindexes[i][j]
                WarpDFS(i+1,j)
        elif a == 1:
            if i>0 and warpjudgeindexes[i-1][j] == -1 and S[i-1][j]==".":
                warpjudgeindexes[i -1][j] = warpjudgeindexes[i][j]
                WarpDFS(i-1,j)
                
        elif a == 2:
            if j+1<W and warpjudgeindexes[i][j+1] == -1 and S[i][j+1]==".":
                warpjudgeindexes[i][j+1] = warpjudgeindexes[i][j]
                WarpDFS(i,j+1)
            
        elif a == 3:
            if j>0 and warpjudgeindexes[i][j-1] == -1 and S[i][j-1]==".":
                warpjudgeindexes[i][j-1] = warpjudgeindexes[i][j]
                WarpDFS(i, j - 1)


def warp(a,b):
    for i in range(5):
        for j in range(5):
            u = a + i - 2
            v = b + j - 2
            if u < 0 or u >= H or v < 0 or v >= W:
                continue
            if indexes[u][v] == -1 and S[u][v] == ".":
                global nextIndex
                indexes[u][v] = nextIndex
                warpjudgeindexes[u][v]=nextIndex
                requiredWarps.append(requiredWarps[indexes[a][b]] + 1)                
                nextIndex+=1
                oneareaSearch(u, v)
            elif requiredWarps[indexes[u][v]] > requiredWarps[indexes[a][b]] + 1 and S[u][v] == ".":
                requiredWarps[indexes[u][v]]=requiredWarps[indexes[a][b]] + 1
                
def oneareaSearch(i, j):
    DFS(i, j)
    WarpDFS(i,j)

requiredWarps.append(0)
nextIndex += 1
indexes[ch][cw] = 0
warpjudgeindexes[ch][cw]=0
oneareaSearch(ch, cw)

if indexes[dh][dw] == -1:
    print("-1")
else:   
    print(requiredWarps[indexes[dh][dw]])

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, shortest_path


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Ch, Cw = Ch-1, Cw-1
    addr_c = Ch*W+Cw
    Dh, Dw = map(int, input().split())
    Dh, Dw = Dh-1, Dw-1
    addr_d = Dh*W+Dw
    #print(addr_c, addr_d)
    g = np.full((H*W, H*W), np.inf)
    S = []  #S[w][h]でアクセス すなわちy,x
    for _ in range(W):
        S.append([True if x=='.' else False for x in input()])
    
    for x, y in itertools.product(range(H), range(W)):
        addr = x*W + y
        if not S[y][x]:
            continue
        for xx, yy in [(x,y+1), (x, y-1), (x+1, y), (x-1, y)]:
            if xx<0 or yy<0 or xx>=H or yy>=W:
                continue
            if S[yy][xx]:
                #print(f"{x},{y} -> {xx}, {yy}")
                addr2 = xx*W + yy
                g[addr, addr2] = 0
                g[addr2, addr] = 0
        for xx, yy in [(x,y+2), (x, y-2), (x+2, y), (x-2, y)]:
            if xx<0 or yy<0 or xx>=H or yy>=W:
                continue
            if S[yy][xx]:
                #print(f"{x},{y} => {xx}, {yy}")
                addr2 = xx*W + yy
                g[addr, addr2] = 1
                g[addr2, addr] = 1
    #print(g)
    #G2_masked = np.ma.masked_invalid(g)
    #print(G2_masked)
    #print(type(G2_masked))
    G2_sparse = csgraph_from_dense(g, null_value=np.inf)
    #print(G2_sparse)
    #print(type(G2_sparse))
    path = shortest_path(G2_sparse, indices=addr_c)
    if path[addr_d] != np.inf:
        print(int(path[addr_d]))
    else:
        print(-1)




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import deque, defaultdict

readline = stdin.readline

def main():
    H, W = map(int, readline().rstrip().split())
    CH, CW = map(lambda x: int(x - 1), readline().rstrip().split())
    DH, DW = map(lambda x: int(x - 1), readline().rstrip().split())
    S = [readline().rstrip() for _ in range(H)]
    v = defaultdict(lambda : False)
    dq = deque([(0, CH, CW)])
    while dq:
        d, h, w = dq.popleft()
        # print(f'{c} : {h} : {w} : {S[h][w]}')
        if (h, w) == (DH, DW):
            print(d)
            exit()
        if v[(h, w)]:
            continue
        v[(h, w)] = True
        for mh, mw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nh = mh + h
            nw = mw + wa
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[(nh, nw)]:
                dq.appendleft([d, nh, nw])
        for mh in range(-2, 3):
            for mw in range(-2, 3):
                if h == w == 0:
                    continue
                nh = mh + h
                nw = mw + w
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[(nh, nw)]:
                    dq.append([d + 1, nh, nw])
    print(-1)

if __name__ == "__main__":
    main()