Buggy python submission (verdict: Time Limit Exceeded):
# 参考: White_Pie_46
# https://atcoder.jp/contests/abc176/submissions/16168825
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    can_walk = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                warping = True
                if h == 0 == w:
                    continue
                if (h, w) in can_walk:
                    warping = False
                yield (h, w, warping)
    warp_can_reach = tuple(gen_warp_can_reach())
    qu = deque()
    qu.append((init_h, init_w, 0))  # 座標とワープ回数を保持

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if grid[h][w] == 'R':
            # 同じマスを複数回キューに追加しているかもしれない。
            # 短距離で調査済みなら再調査は不要。
            continue
        grid[h][w] = 'R'  # reached

        for h_delta, w_delta, warping in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    if warping:
                        qu.append((new_h, new_w, warps + 1))
                    else:
                        qu.appendleft((new_h, new_w, warps))
    return -1


if __name__ == '__main__':
    print(main())


Fixed submission:
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    arrived_total = set()
    arrived_total.add((init_h, init_w))
    distances = [[-1] * width for _ in range(height)]
    warp_count = 0

    def append_qu(now_h, now_w, next_go_to):
        """行き先へ進めそうならキューに追加し， arrived_total に記録する。"""
        for h_delta, w_delta in next_go_to:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if (new_h, new_w) in arrived_total:
                continue
            if grid[new_h][new_w] == '#':
                arrived_total.add((new_h, new_w))
                continue
            qu.append((new_h, new_w))
            arrived_total.add((new_h, new_w))

    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            h, w = qu.popleft()
            distances[h][w] = warp_count
            arrived_set_by_cost.add((h, w))
            append_qu(h, w, adjacents)

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            append_qu(h, w, warp_can_reach)

    return distances[dest_h][dest_w]


if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
# 参考: White_Pie_46
# https://atcoder.jp/contests/abc176/submissions/16168825
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)
    warp_can_reach = tuple(gen_warp_can_reach())
    qu = deque()
    qu.append((init_h, init_w, 0))  # 座標とワープ回数を保持
    reached = set()

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if (h, w) in reached:
            # 同じマスを複数回キューに追加しているかもしれない。
            # 短距離で調査済みなら再調査は不要。
            continue
        reached.add((h, w))

        for h_delta, w_delta in adjacents:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    if (new_h, new_w) not in reached:
                        qu.appendleft((new_h, new_w, warps))

        for h_delta, w_delta in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    if (new_h, new_w) not in reached:
                        qu.append((new_h, new_w, warps + 1))
    return -1


if __name__ == '__main__':
    print(main())


Fixed submission:
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    arrived_total = set()
    arrived_total.add((init_h, init_w))
    distances = [[-1] * width for _ in range(height)]
    warp_count = 0

    def append_qu(now_h, now_w, next_go_to):
        """行き先へ進めそうならキューに追加し， arrived_total に記録する。"""
        for h_delta, w_delta in next_go_to:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if (new_h, new_w) in arrived_total:
                continue
            if grid[new_h][new_w] == '#':
                arrived_total.add((new_h, new_w))
                continue
            qu.append((new_h, new_w))
            arrived_total.add((new_h, new_w))

    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            h, w = qu.popleft()
            distances[h][w] = warp_count
            arrived_set_by_cost.add((h, w))
            append_qu(h, w, adjacents)

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            append_qu(h, w, warp_can_reach)

    return distances[dest_h][dest_w]


if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
# 参考: White_Pie_46
# https://atcoder.jp/contests/abc176/submissions/16168825
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)
    warp_can_reach = tuple(gen_warp_can_reach())
    qu = deque()
    qu.append((init_h, init_w, 0))  # 座標とワープ回数を保持

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if grid[h][w] == 'R':
            # 同じマスを複数回キューに追加しているかもしれない。
            # 短距離で調査済みなら再調査は不要。
            continue
        grid[h][w] = 'R'  # reached

        for h_delta, w_delta in adjacents:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if grid[new_h][new_w] == '.':
                qu.appendleft((new_h, new_w, warps))

        for h_delta, w_delta in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if grid[new_h][new_w] == '.':
                qu.append((new_h, new_w, warps + 1))
    return -1


if __name__ == '__main__':
    print(main())


Fixed submission:
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    arrived_total = set()
    arrived_total.add((init_h, init_w))
    distances = [[-1] * width for _ in range(height)]
    warp_count = 0

    def append_qu(now_h, now_w, next_go_to):
        """行き先へ進めそうならキューに追加し， arrived_total に記録する。"""
        for h_delta, w_delta in next_go_to:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if (new_h, new_w) in arrived_total:
                continue
            if grid[new_h][new_w] == '#':
                arrived_total.add((new_h, new_w))
                continue
            qu.append((new_h, new_w))
            arrived_total.add((new_h, new_w))

    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            h, w = qu.popleft()
            distances[h][w] = warp_count
            arrived_set_by_cost.add((h, w))
            append_qu(h, w, adjacents)

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            append_qu(h, w, warp_can_reach)

    return distances[dest_h][dest_w]


if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
# 参考: White_Pie_46
# https://atcoder.jp/contests/abc176/submissions/16168825
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)
    warp_can_reach = tuple(gen_warp_can_reach())
    qu = deque()
    qu.append((init_h, init_w, 0))  # 座標とワープ回数を保持

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        grid[h][w] = 'R'  # reached

        for h_delta, w_delta in adjacents:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if grid[new_h][new_w] == '.':
                qu.appendleft((new_h, new_w, warps))

        for h_delta, w_delta in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if grid[new_h][new_w] == '.':
                qu.append((new_h, new_w, warps + 1))
    return -1


if __name__ == '__main__':
    print(main())


Fixed submission:
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    arrived_total = set()
    arrived_total.add((init_h, init_w))
    distances = [[-1] * width for _ in range(height)]
    warp_count = 0

    def append_qu(now_h, now_w, next_go_to):
        """行き先へ進めそうならキューに追加し， arrived_total に記録する。"""
        for h_delta, w_delta in next_go_to:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if (new_h, new_w) in arrived_total:
                continue
            if grid[new_h][new_w] == '#':
                arrived_total.add((new_h, new_w))
                continue
            qu.append((new_h, new_w))
            arrived_total.add((new_h, new_w))

    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            h, w = qu.popleft()
            distances[h][w] = warp_count
            arrived_set_by_cost.add((h, w))
            append_qu(h, w, adjacents)

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            append_qu(h, w, warp_can_reach)

    return distances[dest_h][dest_w]


if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    arrived_total = set()
    arrived_total.add((init_h, init_w))
    distances = [[-1] * width for _ in range(height)]
    warp_count = 0

    def append_qu(now_h, now_w, next_go_to):
        """行き先へ進めそうならキューに追加し， arrived_total に記録する。"""
        for h_delta, w_delta in next_go_to:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if (new_h, new_w) in arrived_total:
                continue
            if grid[new_h][new_w] == '#':
                arrived_total.add((new_h, new_w))
                continue
            qu.append((new_h, new_w))
            arrived_total.add((new_h, new_w))

    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            h, w = qu.popleft()
            distances[h][w] = warp_count
            arrived_set_by_cost.add((h, w))
            append_qu(h, w, adjacents)

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            append_qu(h, w, warp_can_reach)

    return distances[dest_h][dest_w]


if __name__ == '__main__':
    print(main())


Fixed submission:
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    arrived_total = set()
    arrived_total.add((init_h, init_w))
    distances = [[-1] * width for _ in range(height)]
    warp_count = 0

    def append_qu(now_h, now_w, next_go_to):
        """行き先へ進めそうならキューに追加し， arrived_total に記録する。"""
        for h_delta, w_delta in next_go_to:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if (new_h, new_w) in arrived_total:
                continue
            if grid[new_h][new_w] == '#':
                arrived_total.add((new_h, new_w))
                continue
            qu.append((new_h, new_w))
            arrived_total.add((new_h, new_w))

    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            h, w = qu.popleft()
            distances[h][w] = warp_count
            arrived_set_by_cost.add((h, w))
            append_qu(h, w, adjacents)

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            append_qu(h, w, warp_can_reach)

    return distances[dest_h][dest_w]


if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]

    INF = height * width + 1
    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    arrived = [[-1] * width for _ in range(height)]
    warp_count = 0
    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            now_h, now_w = qu.popleft()
            arrived[now_h][now_w] = warp_count
            arrived_set_by_cost.add((now_h, now_w))
            for h_delta, w_delta in adjacents:
                new_h, new_w = now_h + h_delta, now_w + w_delta
                if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                    continue
                if arrived[new_h][new_w] != -1:
                    continue
                if grid[new_h][new_w] == '#':
                    arrived[new_h][new_w] = INF
                    continue
                qu.append((new_h, new_w))

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            for h_delta, w_delta in warp_can_reach:
                new_h, new_w = h + h_delta, w + w_delta
                if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                    continue
                if arrived[new_h][new_w] != -1:
                    continue
                if grid[new_h][new_w] == '#':
                    arrived[new_h][new_w] = INF
                    continue
                qu.append((new_h, new_w))
    return arrived[dest_h][dest_w]


if __name__ == '__main__':
    print(main())


Fixed submission:
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    arrived_total = set()
    arrived_total.add((init_h, init_w))
    distances = [[-1] * width for _ in range(height)]
    warp_count = 0

    def append_qu(now_h, now_w, next_go_to):
        """行き先へ進めそうならキューに追加し， arrived_total に記録する。"""
        for h_delta, w_delta in next_go_to:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if (new_h, new_w) in arrived_total:
                continue
            if grid[new_h][new_w] == '#':
                arrived_total.add((new_h, new_w))
                continue
            qu.append((new_h, new_w))
            arrived_total.add((new_h, new_w))

    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            h, w = qu.popleft()
            distances[h][w] = warp_count
            arrived_set_by_cost.add((h, w))
            append_qu(h, w, adjacents)

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            append_qu(h, w, warp_can_reach)

    return distances[dest_h][dest_w]


if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]

    INF = 10 ** 7
    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    qu_append = qu.append
    qu_popleft = qu.popleft
    arrived = [[-1] * width for _ in range(height)]
    warp_count = 0
    while qu:
        arrived_set_by_cost = set()
        arrived_set_by_cost_add = arrived_set_by_cost.add
        # ワープなしのBFS
        while qu:
            now_h, now_w = qu_popleft()
            arrived[now_h][now_w] = warp_count
            arrived_set_by_cost_add((now_h, now_w))
            for h_delta, w_delta in adjacents:
                new_h, new_w = now_h + h_delta, now_w + w_delta
                if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                    continue
                if arrived[new_h][new_w] != -1:
                    continue
                if grid[new_h][new_w] == '#':
                    arrived[new_h][new_w] = INF
                    continue
                qu_append((new_h, new_w))

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            for h_delta, w_delta in warp_can_reach:
                new_h, new_w = h + h_delta, w + w_delta
                if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                    continue
                if arrived[new_h][new_w] != -1:
                    continue
                if grid[new_h][new_w] == '#':
                    arrived[new_h][new_w] = INF
                    continue
                qu_append((new_h, new_w))
    return arrived[dest_h][dest_w]


if __name__ == '__main__':
    print(main())


Fixed submission:
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    arrived_total = set()
    arrived_total.add((init_h, init_w))
    distances = [[-1] * width for _ in range(height)]
    warp_count = 0

    def append_qu(now_h, now_w, next_go_to):
        """行き先へ進めそうならキューに追加し， arrived_total に記録する。"""
        for h_delta, w_delta in next_go_to:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if (new_h, new_w) in arrived_total:
                continue
            if grid[new_h][new_w] == '#':
                arrived_total.add((new_h, new_w))
                continue
            qu.append((new_h, new_w))
            arrived_total.add((new_h, new_w))

    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            h, w = qu.popleft()
            distances[h][w] = warp_count
            arrived_set_by_cost.add((h, w))
            append_qu(h, w, adjacents)

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            append_qu(h, w, warp_can_reach)

    return distances[dest_h][dest_w]


if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    qu_append = qu.append
    qu_popleft = qu.popleft
    arrived = [[-1] * width for _ in range(height)]
    warp_count = 0
    while qu:
        arrived_set_by_cost = set()
        arrived_set_by_cost_add = arrived_set_by_cost.add
        # ワープなしのBFS
        while qu:
            now_h, now_w = qu_popleft()
            arrived[now_h][now_w] = warp_count
            arrived_set_by_cost_add((now_h, now_w))
            for h_delta, w_delta in adjacents:
                new_h, new_w = now_h + h_delta, now_w + w_delta
                if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                    continue
                if grid[new_h][new_w] == '#':
                    continue
                if arrived[new_h][new_w] != -1:
                    continue
                qu_append((new_h, new_w))

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            for h_delta, w_delta in warp_can_reach:
                new_h, new_w = h + h_delta, w + w_delta
                if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                    continue
                if grid[new_h][new_w] == '#':
                    continue
                if arrived[new_h][new_w] != -1:
                    continue
                qu_append((new_h, new_w))
    return arrived[dest_h][dest_w]


if __name__ == '__main__':
    print(main())


Fixed submission:
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    arrived_total = set()
    arrived_total.add((init_h, init_w))
    distances = [[-1] * width for _ in range(height)]
    warp_count = 0

    def append_qu(now_h, now_w, next_go_to):
        """行き先へ進めそうならキューに追加し， arrived_total に記録する。"""
        for h_delta, w_delta in next_go_to:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if (new_h, new_w) in arrived_total:
                continue
            if grid[new_h][new_w] == '#':
                arrived_total.add((new_h, new_w))
                continue
            qu.append((new_h, new_w))
            arrived_total.add((new_h, new_w))

    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            h, w = qu.popleft()
            distances[h][w] = warp_count
            arrived_set_by_cost.add((h, w))
            append_qu(h, w, adjacents)

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            append_qu(h, w, warp_can_reach)

    return distances[dest_h][dest_w]


if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    arrived = [[-1] * width for _ in range(height)]
    warp_count = 0
    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            now_h, now_w = qu.popleft()
            arrived[now_h][now_w] = warp_count
            arrived_set_by_cost.add((now_h, now_w))
            for h_delta, w_delta in adjacents:
                new_h, new_w = now_h + h_delta, now_w + w_delta
                if new_h < 0 or new_h >= height:
                    continue
                if new_w < 0 or new_w >= width:
                    continue
                if arrived[new_h][new_w] != -1:
                    continue
                if grid[new_h][new_w] == '#':
                    continue
                qu.append((new_h, new_w))

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            for h_delta, w_delta in warp_can_reach:
                new_h, new_w = h + h_delta, w + w_delta
                if new_h < 0 or new_h >= height:
                    continue
                if new_w < 0 or new_w >= width:
                    continue
                if arrived[new_h][new_w] != -1:
                    continue
                if grid[new_h][new_w] == '#':
                    continue
                qu.append((new_h, new_w))
    return arrived[dest_h][dest_w]


if __name__ == '__main__':
    print(main())


Fixed submission:
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    arrived_total = set()
    arrived_total.add((init_h, init_w))
    distances = [[-1] * width for _ in range(height)]
    warp_count = 0

    def append_qu(now_h, now_w, next_go_to):
        """行き先へ進めそうならキューに追加し， arrived_total に記録する。"""
        for h_delta, w_delta in next_go_to:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if (new_h, new_w) in arrived_total:
                continue
            if grid[new_h][new_w] == '#':
                arrived_total.add((new_h, new_w))
                continue
            qu.append((new_h, new_w))
            arrived_total.add((new_h, new_w))

    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            h, w = qu.popleft()
            distances[h][w] = warp_count
            arrived_set_by_cost.add((h, w))
            append_qu(h, w, adjacents)

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            append_qu(h, w, warp_can_reach)

    return distances[dest_h][dest_w]


if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]
    INF = 10 ** 3

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    arrived = [[-1] * width for _ in range(height)]
    warp_count = 0
    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            now_h, now_w = qu.popleft()
            arrived[now_h][now_w] = warp_count
            arrived_set_by_cost.add((now_h, now_w))
            for adj_h, adj_w in adjacents:
                candidate_h, candidate_w = now_h + adj_h, now_w + adj_w
                if candidate_h < 0 or candidate_h >= height:
                    continue
                if candidate_w < 0 or candidate_w >= width:
                    continue
                if arrived[candidate_h][candidate_w] != -1:
                    continue
                if grid[candidate_h][candidate_w] == '#':
                    arrived[candidate_h][candidate_w] = INF
                    continue
                qu.append((candidate_h, candidate_w))

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            for h_delta, w_delta in warp_can_reach:
                new_h, new_w = h + h_delta, w + w_delta
                if new_h < 0 or new_h >= height:
                    continue
                if new_w < 0 or new_w >= width:
                    continue
                if arrived[new_h][new_w] != -1:
                    continue
                if grid[new_h][new_w] == '#':
                    arrived[new_h][new_w] = INF
                    continue
                qu.append((new_h, new_w))
    return arrived[dest_h][dest_w]


if __name__ == '__main__':
    print(main())


Fixed submission:
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    arrived_total = set()
    arrived_total.add((init_h, init_w))
    distances = [[-1] * width for _ in range(height)]
    warp_count = 0

    def append_qu(now_h, now_w, next_go_to):
        """行き先へ進めそうならキューに追加し， arrived_total に記録する。"""
        for h_delta, w_delta in next_go_to:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if (new_h, new_w) in arrived_total:
                continue
            if grid[new_h][new_w] == '#':
                arrived_total.add((new_h, new_w))
                continue
            qu.append((new_h, new_w))
            arrived_total.add((new_h, new_w))

    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            h, w = qu.popleft()
            distances[h][w] = warp_count
            arrived_set_by_cost.add((h, w))
            append_qu(h, w, adjacents)

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            append_qu(h, w, warp_can_reach)

    return distances[dest_h][dest_w]


if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]
    INF = 10 ** 3

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    arrived = [[-1] * width for _ in range(height)]
    warp_count = 0
    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            now_h, now_w = qu.popleft()
            arrived[now_h][now_w] = warp_count
            arrived_set_by_cost.add((now_h, now_w))
            for adj_h, adj_w in adjacents:
                candidate_h, candidate_w = now_h + adj_h, now_w + adj_w
                if candidate_h < 0 or candidate_h >= height:
                    continue
                if candidate_w < 0 or candidate_w >= width:
                    continue
                if arrived[candidate_h][candidate_w] != -1:
                    continue
                if grid[candidate_h][candidate_w] == '#':
                    arrived[candidate_h][candidate_w] = INF
                    continue
                qu.append((candidate_h, candidate_w))

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            for h_delta, w_delta in warp_can_reach:
                new_h, new_w = h + h_delta, w + w_delta
                if new_h < 0 or new_h >= height:
                    continue
                if new_w < 0 or new_w >= width:
                    continue
                if arrived[new_h][new_w] != -1:
                    continue
                if grid[new_h][new_w] == '#':
                    arrived[new_h][new_w] = INF
                    continue
                qu.append((new_h, new_w))
    return arrived[dest_h][dest_w]


if __name__ == '__main__':
    print(main())


Fixed submission:
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [input() for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    arrived_total = set()
    arrived_total.add((init_h, init_w))
    distances = [[-1] * width for _ in range(height)]
    warp_count = 0

    def append_qu(now_h, now_w, next_go_to):
        """行き先へ進めそうならキューに追加し， arrived_total に記録する。"""
        for h_delta, w_delta in next_go_to:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if (new_h, new_w) in arrived_total:
                continue
            if grid[new_h][new_w] == '#':
                arrived_total.add((new_h, new_w))
                continue
            qu.append((new_h, new_w))
            arrived_total.add((new_h, new_w))

    while qu:
        arrived_set_by_cost = set()
        # ワープなしのBFS
        while qu:
            h, w = qu.popleft()
            distances[h][w] = warp_count
            arrived_set_by_cost.add((h, w))
            append_qu(h, w, adjacents)

        warp_count += 1
        # 1回ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            append_qu(h, w, warp_can_reach)

    return distances[dest_h][dest_w]


if __name__ == '__main__':
    print(main())