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


def main():
    from sys import stdin
    readline = stdin.readline

    from builtins import max, min, range

    INF = 10 ** 6

    H, W = map(int, readline().split())
    Ch, Cw = map(lambda x: int(x) - 1, readline().split())
    Dh, Dw = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    warp_count = 0
    warpq = []
    while q:
        while q:
            warpq.append(q[0])
            h, w = q.popleft()
            if h - 1 >= 0 and t[h - 1][w] > warp_count:
                q.append((h - 1, w))
                t[h - 1][w] = warp_count
            if h + 1 < H and t[h + 1][w] > warp_count:
                q.append((h + 1, w))
                t[h + 1][w] = warp_count
            if w - 1 >= 0 and t[h][w - 1] > warp_count:
                q.append((h, w - 1))
                t[h][w - 1] = warp_count
            if w + 1 < W and t[h][w + 1] > warp_count:
                q.append((h, w + 1))
                t[h][w + 1] = warp_count

        if t[Dh][Dw] != INF:
            break

        warp_count += 1
        for h, w in warpq:
            for i in range(max(0, h - 2), min(H, h + 3)):
                ti = t[i]
                for j in range(max(0, w - 2), min(W, w + 3)):
                    if ti[j] > warp_count:
                        ti[j] = warp_count
                        q.append((i, j))
        warpq.clear()

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()


Fixed submission:
from collections import deque

INF = float('inf')

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

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])

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


def main():
    from sys import stdin
    readline = stdin.readline

    from builtins import max, min, range

    INF = float('inf')

    H, W = map(int, readline().split())
    Ch, Cw = map(lambda x: int(x) - 1, readline().split())
    Dh, Dw = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    a = 0
    while q:
        warpq = []
        while q:
            h, w = q.popleft()
            warpq.append((h, w))
            if h - 1 >= 0 and t[h - 1][w] > a:
                q.append((h - 1, w))
                t[h - 1][w] = a
            if h + 1 < H and t[h + 1][w] > a:
                q.append((h + 1, w))
                t[h + 1][w] = a
            if w - 1 >= 0 and t[h][w - 1] > a:
                q.append((h, w - 1))
                t[h][w - 1] = a
            if w + 1 < W and t[h][w + 1] > a:
                q.append((h, w + 1))
                t[h][w + 1] = a

        if t[Dh][Dw] != INF:
            break

        a += 1
        for h, w in warpq:
            for i in range(max(0, h - 2), min(H, h + 3)):
                ti = t[i]
                for j in range(max(0, w - 2), min(W, w + 3)):
                    if ti[j] <= a:
                        continue
                    ti[j] = a
                    q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()


Fixed submission:
from collections import deque

INF = float('inf')

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

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])

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


def main():
    from sys import stdin
    readline = stdin.readline

    from builtins import max, min, range

    INF = float('inf')

    H, W = map(int, readline().split())
    Ch, Cw = map(lambda x: int(x) - 1, readline().split())
    Dh, Dw = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    while q:
        warpq = []
        while q:
            h, w = q.popleft()
            a = t[h][w]
            warpq.append((h, w))
            if h - 1 >= 0 and t[h - 1][w] > a:
                q.append((h - 1, w))
                t[h - 1][w] = a
            if h + 1 < H and t[h + 1][w] > a:
                q.append((h + 1, w))
                t[h + 1][w] = a
            if w - 1 >= 0 and t[h][w - 1] > a:
                q.append((h, w - 1))
                t[h][w - 1] = a
            if w + 1 < W and t[h][w + 1] > a:
                q.append((h, w + 1))
                t[h][w + 1] = a

        if t[Dh][Dw] != INF:
            break

        for h, w in warpq:
            for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
                ti = t[i]
                for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                    if ti[j] <= a + 1:
                        continue
                    ti[j] = a + 1
                    q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()


Fixed submission:
from collections import deque

INF = float('inf')

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

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])

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


def main():
    from sys import stdin
    readline = stdin.readline

    INF = float('inf')

    H, W = map(int, readline().split())
    Ch, Cw = map(lambda x: int(x) - 1, readline().split())
    Dh, Dw = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    while q:
        warpq = []
        while q:
            h, w = q.popleft()
            a = t[h][w]
            warpq.append((h, w))
            if h - 1 >= 0 and t[h - 1][w] > a:
                q.append((h - 1, w))
                t[h - 1][w] = a
            if h + 1 < H and t[h + 1][w] > a:
                q.append((h + 1, w))
                t[h + 1][w] = a
            if w - 1 >= 0 and t[h][w - 1] > a:
                q.append((h, w - 1))
                t[h][w - 1] = a
            if w + 1 < W and t[h][w + 1] > a:
                q.append((h, w + 1))
                t[h][w + 1] = a

        if t[Dh][Dw] != INF:
            break

        for h, w in warpq:
            for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
                ti = t[i]
                for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                    if ti[j] <= a + 1:
                        continue
                    ti[j] = a + 1
                    q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()


Fixed submission:
from collections import deque

INF = float('inf')

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

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])

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


def main():
    from sys import stdin
    readline = stdin.readline

    INF = float('inf')

    H, W = map(int, readline().split())
    Ch, Cw = map(lambda x: int(x) - 1, readline().split())
    Dh, Dw = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    while q:
        warpq = []
        while q:
            h, w = q.popleft()
            a = t[h][w]
            warpq.append((h, w))
            if h - 1 >= 0 and t[h - 1][w] > a:
                q.append((h - 1, w))
                t[h - 1][w] = a
            if h + 1 < H and t[h + 1][w] > a:
                q.append((h + 1, w))
                t[h + 1][w] = a
            if w - 1 >= 0 and t[h][w - 1] > a:
                q.append((h, w - 1))
                t[h][w - 1] = a
            if w + 1 < W and t[h][w + 1] > a:
                q.append((h, w + 1))
                t[h][w + 1] = a

        for h, w in warpq:
            for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
                ti = t[i]
                for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                    if ti[j] <= a + 1:
                        continue
                    ti[j] = a + 1
                    q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()


Fixed submission:
from collections import deque

INF = float('inf')

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

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])

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


def main():
    from sys import stdin
    readline = stdin.readline

    INF = float('inf')

    H, W = map(int, readline().split())
    Ch, Cw = map(lambda x: int(x) - 1, readline().split())
    Dh, Dw = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    while q:
        h, w = q.popleft()
        a = t[h][w]
        if h - 1 >= 0 and t[h - 1][w] > a:
            q.appendleft((h - 1, w))
            t[h - 1][w] = a
        if h + 1 < H and t[h + 1][w] > a:
            q.appendleft((h + 1, w))
            t[h + 1][w] = a
        if w - 1 >= 0 and t[h][w - 1] > a:
            q.appendleft((h, w - 1))
            t[h][w - 1] = a
        if w + 1 < W and t[h][w + 1] > a:
            q.appendleft((h, w + 1))
            t[h][w + 1] = a

        for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
            ti = t[i]
            for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                if ti[j] <= a + 1:
                    continue
                ti[j] = a + 1
                q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()


Fixed submission:
from collections import deque

INF = float('inf')

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

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])

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

from sys import stdin
readline = stdin.readline

INF = float('inf')

H, W = map(int, readline().split())
Ch, Cw = map(lambda x: int(x) - 1, readline().split())
Dh, Dw = map(lambda x: int(x) - 1, readline().split())
S = [readline()[:-1] for _ in range(H)]

t = [[INF] * W for _ in range(H)]
for h in range(H):
    th = t[h]
    Sh = S[h]
    for w in range(W):
        if Sh[w] == '#':
            th[w] = -1

t[Ch][Cw] = 0
q = deque([(Ch, Cw)])
while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        ti = t[i]
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if ti[j] <= a + 1:
                continue
            ti[j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])


Fixed submission:
from collections import deque

INF = float('inf')

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

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])

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

    INF = float('inf')

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

    t = [[INF] * W for _ in range(H)]
    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])

    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    while q:
        h, w = q.popleft()
        a = t[h][w]
        if h - 1 >= 0 and t[h - 1][w] > a:
            q.appendleft((h - 1, w))
            t[h - 1][w] = a
        if h + 1 < H and t[h + 1][w] > a:
            q.appendleft((h + 1, w))
            t[h + 1][w] = a
        if w - 1 >= 0 and t[h][w - 1] > a:
            q.appendleft((h, w - 1))
            t[h][w - 1] = a
        if w + 1 < W and t[h][w + 1] > a:
            q.appendleft((h, w + 1))
            t[h][w + 1] = a

        for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
            ti = t[i]
            for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                if ti[j] <= a + 1:
                    continue
                ti[j] = a + 1
                q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()


Fixed submission:
from collections import deque

INF = float('inf')

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

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])

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

    INF = float('inf')

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

    t = [[INF] * W for _ in range(H)]
    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])

    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                t[h][w] = -1

    while q:
        h, w = q.popleft()
        a = t[h][w]
        if h - 1 >= 0 and t[h - 1][w] > a:
            q.appendleft((h - 1, w))
            t[h - 1][w] = a
        if h + 1 < H and t[h + 1][w] > a:
            q.appendleft((h + 1, w))
            t[h + 1][w] = a
        if w - 1 >= 0 and t[h][w - 1] > a:
            q.appendleft((h, w - 1))
            t[h][w - 1] = a
        if w + 1 < W and t[h][w + 1] > a:
            q.appendleft((h, w + 1))
            t[h][w + 1] = a

        for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
            for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                if t[i][j] <= a + 1:
                    continue
                t[i][j] = a + 1
                q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()


Fixed submission:
from collections import deque

INF = float('inf')

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

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])

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

INF = float('inf')

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

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            t[h][w] = -1

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])


Fixed submission:
from collections import deque

INF = float('inf')

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

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])

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

    INF = float('inf')

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

    t = [[INF] * W for _ in range(H)]
    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])

    while q:
        h, w = q.popleft()
        a = t[h][w]
        if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
            q.appendleft((h - 1, w))
            t[h - 1][w] = a
        if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
            q.appendleft((h + 1, w))
            t[h + 1][w] = a
        if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
            q.appendleft((h, w - 1))
            t[h][w - 1] = a
        if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
            q.appendleft((h, w + 1))
            t[h][w + 1] = a

        for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
            for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                if S[i][j] == '#':
                    continue
                if t[i][j] <= a + 1:
                    continue
                t[i][j] = a + 1
                q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()


Fixed submission:
from collections import deque

INF = float('inf')

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

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])

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

INF = float('inf')

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

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])


Fixed submission:
from collections import deque

INF = float('inf')

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

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])