Problem p02579 (python)

Fixed submission:
import sys
from io import StringIO
import unittest
import os
from collections import deque

# 再帰処理上限(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())


# TODO 迷路クラスを作成してみた。これは、共通化しておく必要がある。
# 迷路(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])

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

        # 処理済みなら何もしない(移動したければ編集するといい)
        # 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 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()

    # UnionFindにて集合を明確にする。
    uf = UnionFind(maze.getcellcount())

    que = deque()
    que.extend(start_list)

    # スタート地点の候補数だけ、BFSを行う(今回の問題固有で必要なループ)
    # BFS開始
    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())]

    # BFS開始
    maze.reset_arrived()  # 到達情報を初期化(これをしておかないと、以下のBFSが動かない)
    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)

    # スタート地点のエリアからBFSを実施。
    start_erea = uf.getroot(maze.get1dpoint(start))

    # 初期値：自分のエリアにはワープ回数0回で移動できる
    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()

        # 移動できる対象単位でループ(例；エリア1から、2,3に移動できる、等)
        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)


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

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

Buggy submission (verdict: Runtime Error):
import sys
from io import StringIO
import unittest
import os
from collections import deque

# 再帰処理上限(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())


# 迷路(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])

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

        # 処理済みなら何もしない(移動したければ編集するといい)
        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 get1dpoint(self, cell) -> int:
        """
        座標情報を1次元に変換したものを返す。対象を1次元で管理する処理との連携に使用する。(例：UnionFind)
        """
        # 縦座標×縦幅 + 横座標 等式で、座標を一次元配列の添え字に変換する。
        return cell[0] * len(self.__maze) + 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()

    # UnionFindにて集合を明確にする。
    uf = UnionFind(maze.getcellcount())

    que = deque()
    que.extend(start_list)

    # スタート地点の候補数だけ、BFSを行う(今回の問題固有で必要なループ)
    # BFS開始
    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())]

    # BFS開始
    maze.reset_arrived()  # 到達情報を初期化(これをしておかないと、以下のBFSが動かない)
    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)

    # スタート地点のエリアからBFSを実施。
    start_erea = uf.getroot(maze.get1dpoint(start))

    # 初期値：自分のエリアにはワープ回数0回で移動できる
    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()

        # 移動できる対象単位でループ(例；エリア1から、2,3に移動できる、等)
        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)


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

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

Buggy submission (verdict: Runtime Error):
import sys
from io import StringIO
import unittest
import os
from collections import deque

# 再帰処理上限(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())


# 迷路(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])

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

        # 処理済みなら何もしない(移動したければ編集するといい)
        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 get1dpoint(self, cell) -> int:
        """
        座標情報を1次元に変換したものを返す。対象を1次元で管理する処理との連携に使用する。(例：UnionFind)
        """
        # 縦座標×縦幅 + 横座標 等式で、座標を一次元配列の添え字に変換する。
        return cell[0] * len(self.__maze) + 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()

    # UnionFindにて集合を明確にする。
    uf = UnionFind(maze.getcellcount())

    que = deque()
    que.extend(start_list)

    # スタート地点の候補数だけ、BFSを行う(今回の問題固有で必要なループ)
    # BFS開始
    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())]

    # BFS開始
    maze.reset_arrived()  # 到達情報を初期化(これをしておかないと、以下のBFSが動かない)
    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, 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

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

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

    # スタート地点のエリアからBFSを実施。
    start_erea = uf.getroot(maze.get1dpoint(start))

    # 初期値：自分のエリアにはワープ回数0回で移動できる
    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()

        # 移動できる対象単位でループ(例；エリア1から、2,3に移動できる、等)
        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)


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

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

Buggy submission (verdict: Runtime Error):
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()

Buggy submission (verdict: Runtime Error):
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]


# 実装を行う関数
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()))

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

    h += 1
    w += 1

    # ブロックで囲む
    maze = [["#" for _ in range(w)]]
    for line in work_maze:
        maze.append(["#"] + line + ["#"])
    maze.append([["#" for _ in range(w)]])

    # スタート地点の候補を選定する
    start_list = []
    for i in range(1, h):
        for j in range(1, w):
            # 自分が壁なら対象外
            if maze[i][j] == "#":
                continue
            start_list.append([i, j])

    # 集合の分類(-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 1 <= target[0] < h or not 1 <= target[1] < w:
                continue

            # 処理済みなら何もしない
            if ed_list[target[0]][target[1]] != -1:
                continue

            # 壁なら何もしない
            if maze[target[0]][target[1]] == "#":
                continue

            ed_list[target[0]][target[1]] = 1
            uf.union(getpoint(now), getpoint(target))

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

    # 移動できるか確認
    que.extend(start_list)

    # BFS開始
    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 1 <= target[0] < h or not 1 <= target[1] < w:
                continue

            if maze[target[0]][target[1]] == "#":
                continue

            if uf.is_same(getpoint(now), getpoint(target)):
                continue

            move_list[uf.getroot(getpoint(now))].append(uf.getroot(getpoint(target)))

    moved_list = [-1 for a in range(h * w + 1)]
    move_list = [set(a) for a in move_list]

    que.append(uf.getroot(getpoint(start)))
    while len(que) is not 0:
        now = que.pop()
        movetarget = move_list[now]

        for aaa in movetarget:

            # 距離が設定済みなら何もしない
            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()

Buggy submission (verdict: Runtime Error):
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
    return h * point[0] + point[1] - h


# 実装を行う関数
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 = [list(input()) for i in range(h)]

    # スタート地点の候補を選定する
    start_list = []
    for i_len, i in enumerate(range(h)):
        for j_len, j in enumerate(range(w)):
            # 自分が壁なら対象外
            if maze[i][j] == "#":
                continue
            start_list.append([i_len, j_len])

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

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

    que = deque()
    que.extend(start_list)

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

        # 各方向に集合が存在するか確認
        for i, j in [(1, 0), (0, 1), (0, -1), (-1, 0)]:
            # 処理対象の座標
            target = [now[0] + i, now[1] + j]

            # 処理対象のチェック
            # 外なら何もしない
            if not 0 <= target[0] < h or not 0 <= target[1] < w:
                continue

            # 処理済みなら何もしない
            if ed_list[target[0]][target[1]] != -1:
                continue

            ed_list[target[0]][target[1]] = 1

            # 壁なら結合しない
            if maze[target[0]][target[1]] == "#":
                # ng_uf_list.append(getpoint(target))
                continue

            uf.union(getpoint(target), getpoint(now))

    # 探索処理
    # ng_uf_list = set(ng_uf_list)

    move_list = [[] for i in range(h * w)]

    # 移動できるか確認
    que.extend(start_list)

    # BFS開始
    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 0 <= target[0] < h or not 0 <= target[1] < w:
                continue

            if maze[target[0]][target[1]] == "#":
                continue

            if uf.is_same(getpoint(now), getpoint(target)):
                continue

            move_list[uf.getroot(getpoint(now))].append(uf.getroot(getpoint(target)))

    moved_list = [0 for a in range(h * w)]
    move_list = [set(a) for a in move_list]

    que.append(uf.getroot(getpoint(start)))
    while len(que) is not 0:
        now = que.pop()
        movetarget = move_list[now]

        for aaa in movetarget:

            # 距離が設定済みなら何もしない
            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()