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


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# 正解ではない

from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    d = [[-1 for i in range(W)] for j in range(H)]
    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))
    resolve(q, d, S, (Dh - 1, Dw - 1), H, W)
    print(d[Dh - 1][Dw - 1])


def resolve(q, d, S, D, H, W):
    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                elif abs(i) + abs(j) >= 2:
                    q.append((worp_count + 1, nx, ny))


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

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


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))
    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(q, S, D, H, W):
    while len(q):
        worp_count, x, y = q.popleft()
        S[x][y] = '/'

        if (x, y) == D:
            return worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            if 0 <= x + i < H and 0 <= y + j < W and S[x + i][y + j] == '.':
                if abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, x + i, y + j))
                else:
                    q.append((worp_count + 1, x + i, y + j))

    return -1


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# 正解ではない

from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))
    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(q, S, D, H, W):
    while len(q):
        worp_count, x, y = q.popleft()
        S[x][y] = '/'

        if (x, y) == D:
            return worp_count

        for i, j in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
            if 0 <= i < H and 0 <= j < W and S[i][j] in ('.', '1'):
                q.appendleft((worp_count, i, j))
                S[i][j] = '0'

        for i, j in ((x + a, y + b) for a in range(-2, 3) for b in range(-2, 3)):
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.append((worp_count + 1, i, j))
                S[i][j] = '1'

    return -1


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# 正解ではない

from queue import PriorityQueue


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = PriorityQueue(H * W)
    q.put((0, (Ch - 1, Cw - 1)))

    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(q, S, D, H, W):
    while not q.empty():
        worp_count, (x, y) = q.get()
        S[x][y] = '/'

        if (x, y) == D:
            return worp_count

        for i, j in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
            if 0 <= i < H and 0 <= j < W and S[i][j] in ('.', '1'):
                q.put((worp_count, (i, j)))
                S[i][j] = '0'

        for i, j in ((x + a, y + b) for a in range(-2, 3) for b in range(-2, 3)):
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count + 1, (i, j)))
                S[i][j] = '1'

    return -1


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from queue import PriorityQueue


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = PriorityQueue(H * W)
    q.put((0, (Ch - 1, Cw - 1)))

    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(q, S, D, H, W):
    while not q.empty():
        worp_count, (x, y) = q.get()
        S[x][y] = '/'

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] in ('.', '1'):
                q.put((worp_count, (i, j)))
                S[i][j] = '0'

        for i, j in [(x + a, y + b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count + 1, (i, j)))
                S[i][j] = '1'

    return -1


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# 正解ではない

from queue import PriorityQueue

q = PriorityQueue()


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q.put((0, (Ch - 1, Cw - 1)))

    answer = resolve(S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(S, D, H, W):
    while not q.empty():
        worp_count, (x, y) = q.get()
        S[x][y] = '/'

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] in ('.', '1'):
                q.put((worp_count, (i, j)))
                S[i][j] = '0'

        for i, j in [(x + a, y + b) for a in range(-2, 3) for b in range(-2, 3)]:
            if (i, j) in ((x, y), (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
                continue
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count + 1, (i, j)))
                S[i][j] = '1'

    return -1


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# 正解ではない

from queue import PriorityQueue

q = PriorityQueue()


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q.put((0, (Ch - 1, Cw - 1)))

    answer = resolve(S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(S, D, H, W):
    while not q.empty():
        worp_count, (x, y) = q.get()
        S[x][y] = '/'

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] in ('.', '1'):
                q.put((worp_count, (i, j)))
                S[i][j] = '0'

        for i, j in [(x + a, y + b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count + 1, (i, j)))
                S[i][j] = '1'

    return -1


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# 正解ではない

from queue import PriorityQueue

q = PriorityQueue()


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q.put((0, (Ch - 1, Cw - 1)))

    answer = resolve(S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(S, D, H, W):
    while not q.empty():
        worp_count, (x, y) = q.get()
        S[x][y] = '/'

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count, (i, j)))

        for i, j in [(x + a, y + b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count + 1, (i, j)))

    return -1


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# 正解ではない

from queue import Queue

q = Queue()
cell_list = list()


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q.put((0, Ch - 1, Cw - 1))
    S[Ch - 1][Cw - 1] = '/'

    answer = resolve(S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(S, D, H, W):
    while not q.empty():
        worp_count, x, y = q.get()
        cell_list.append((x, y))

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count, i, j))
                S[i][j] = '/'

    for x, y in cell_list:
        for i, j in [(x + a, y + b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count + 1, i, j))
                S[i][j] = '/'

    if q.empty():
        return -1

    return resolve(S, D, H, W)


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# 正解ではない

from queue import Queue

q = Queue()
cell_list = list()


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q.put((0, Ch - 1, Cw - 1))
    S[Ch - 1][Cw - 1] = '1'

    answer = resolve(S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(S, D, H, W):
    if q.empty():
        return -1

    while not q.empty():
        worp_count, x, y = q.get()
        S[x][y] = '2'
        cell_list.append((x, y))

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count, i, j))

    for x, y in cell_list:
        for i, j in [(x + a, y + b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count + 1, i, j))
                S[i][j] = '1'

    return resolve(S, D, H, W)


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from queue import Queue

q = Queue()
cell_list = list()


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q.put((0, Ch - 1, Cw - 1))
    S[Ch - 1][Cw - 1] = '1'

    answer = resolve(S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(S, D, H, W):
    if q.empty():
        return -1

    while not q.empty():
        worp_count, x, y = q.get()
        S[x][y] = '2'
        cell_list.append((x, y))

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count, i, j))

    for x, y in cell_list:
        for i, j in [(a, b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= x + i < H and 0 <= y + j < W and S[x + i][y + j] == '.':
                q.put((worp_count + 1, x + i, y + j))
                S[x + i][y + j] = '1'

    return resolve(S, D, H, W)


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
# 正解ではない

from queue import Queue


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = Queue()
    q.put((0, Ch - 1, Cw - 1))
    S[Ch - 1][Cw - 1] = '1'
    cell_list = list()

    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W, cell_list)
    print(answer)


def resolve(q, S, D, H, W, cell_list):
    while not q.empty():
        worp_count, x, y = q.get()
        S[x][y] = '2'
        cell_list.append((x, y))

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count, i, j))
                S[i][j] = '1'

    if not cell_list:
        return -1

    for x, y in cell_list:
        for i, j in [(a, b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= x + i < H and 0 <= y + j < W and S[x + i][y + j] == '.':
                q.put((worp_count + 1, x + i, y + j))
                S[x + i][y + j] = '1'

    return resolve(q, S, D, H, W, cell_list)


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
# 正解ではない

from queue import Queue


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = Queue()
    q.put((0, Ch - 1, Cw - 1))
    S[Ch - 1][Cw - 1] = '1'

    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(q, S, D, H, W):
    cell_list = list()
    while not q.empty():
        worp_count, x, y = q.get()
        S[x][y] = '2'
        cell_list.append((x, y))

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count, i, j))
                S[i][j] = '1'

    if not cell_list:
        return -1

    for x, y in cell_list:
        for i, j in [(a, b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= x + i < H and 0 <= y + j < W and S[x + i][y + j] == '.':
                q.put((worp_count + 1, x + i, y + j))
                S[x + i][y + j] = '1'

    return resolve(q, S, D, H, W)


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
# 正解ではない

from queue import Queue


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = Queue()
    q.put((0, Ch - 1, Cw - 1))
    S[Ch - 1][Cw - 1] = '1'

    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W)
    print(S)
    print(answer)


def resolve(q, S, D, H, W):
    cell_list = list()
    while not q.empty():
        worp_count, x, y = q.get()
        S[x][y] = '2'
        cell_list.append((x, y))

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count, i, j))
                S[i][j] = '1'

    if not cell_list:
        return -1

    for x, y in cell_list:
        for i, j in [(a, b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= x + i < H and 0 <= y + j < W and S[x + i][y + j] == '.':
                q.put((worp_count + 1, x + i, y + j))
                S[x + i][y + j] = '1'

    return resolve(q, S, D, H, W)


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
# 正解ではない

from queue import Queue


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q1 = Queue()
    q2 = Queue()
    q1.put((0, Ch - 1, Cw - 1))

    answer = resolve(q1, q2, S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(q1, q2, S, D, H, W):
    while not q1.empty():
        worp_count, x, y = q1.get()
        if S[x][y] == '/':
            continue
        S[x][y] = '/'
        q2.put((x, y))

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q1.put((worp_count, i, j))

    if q2.empty():
        return -1

    while not q2.empty():
        x, y = q2.get()
        for i, j in [(a, b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= x + i < H and 0 <= y + j < W and S[x + i][y + j] == '.':
                q1.put((worp_count + 1, x + i, y + j))

    return resolve(q1, q2, S, D, H, W)


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# 正解ではない

from queue import PriorityQueue


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = PriorityQueue()
    q.put((0, (Ch - 1, Cw - 1)))

    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(q, S, D, H, W):
    while not q.empty():
        worp_count, (x, y) = q.get()
        if S[x][y] == '/':
            continue
        S[x][y] = '/'

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count, (i, j)))

        for i, j in [(a, b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= x + i < H and 0 <= y + j < W and S[x + i][y + j] == '.':
                q.put((worp_count + 1, (x + i, y + j)))

    return -1


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# 正解ではない

from queue import PriorityQueue


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = PriorityQueue()
    q.put((0, (Ch - 1, Cw - 1)))

    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(q, S, D, H, W):
    is_empty = True
    while not q.empty():
        worp_count, (x, y) = q.get()
        if S[x][y] == '/':
            continue
        S[x][y] = '/'
        is_empty = False

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count, (i, j)))

        for i, j in [(a, b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= x + i < H and 0 <= y + j < W and S[x + i][y + j] == '.':
                q.put((worp_count + 1, (x + i, y + j)))

    if is_empty:
        return -1

    return resolve(q, S, D, H, W)


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
# 正解ではない

from queue import PriorityQueue


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = PriorityQueue()
    q.put((0, (Ch - 1, Cw - 1)))

    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(q, S, D, H, W):
    is_empty = True
    location_list = set()
    while not q.empty():
        worp_count, (x, y) = q.get()
        S[x][y] = '/'
        is_empty = False

        if (x, y) == D:
            return worp_count

        location_list.add((x, y))
        if 0 <= x - 1 < H and S[x - 1][y] == '.':
            q.put((worp_count, (x - 1, y)))
        elif 0 <= x + 1 < H and S[x + 1][y] == '.':
            q.put((worp_count, (x + 1, y)))
        elif 0 <= y - 1 < W and S[x][y - 1] == '.':
            q.put((worp_count, (x, y - 1)))
        elif 0 <= y + 1 < W and S[x][y + 1] == '.':
            q.put((worp_count, (x, y + 1)))

    if is_empty:
        return -1

    for i in range(-2, 3):
        for j in range(-2, 3):
            for x, y in location_list:
                if 0 <= x + i < H and 0 <= y + j < W and S[x + i][y + j] == '.':
                    q.put((worp_count + 1, (x + i, y + j)))

    return resolve(q, S, D, H, W)


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
from queue import Queue

A = set()
Q = Queue()
H = W = 0
S = []
worps = set()


def main():
    global H, W, Dh, Dw, S
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [input() for i in range(H)]
    Q.put(tuple([Ch, Cw, 0]))

    try:
        while item := Q.get_nowait():
            loop(item)
    except BaseException:
        pass

    print(min(worps)) if worps else print(-1)


def loop(current):
    print(current)
    ci, cj, worp = current
    if (ci, cj) == (Dh, Dw):
        worps.add(worp)

    A.add((ci, cj))
    move1 = False
    for di, dj in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        ni = ci + di
        nj = cj + dj
        if 0 < ni and ni <= H and 0 < nj and nj <= W and \
                S[ni - 1][nj - 1] == '.' and (ni, nj) not in A:
            Q.put((ni, nj, worp))
            move1 = True
    if not move1:
        for di in range(-2, 3):
            for dj in range(-2, 3):
                if (di, dj) == (0, 0):
                    continue
                ni = ci + di
                nj = cj + dj
                if 0 < ni and ni <= H and 0 < nj and nj <= W and \
                        S[ni - 1][nj - 1] == '.' and (ni, nj) not in A:
                    Q.put((ni, nj, worp + 1))

    try:
        while item := Q.get_nowait():
            loop(item)
    except BaseException:
        pass


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()