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


if __name__ == '__main__':

    H, W = map(int, input().split())
    s_h, s_w = map(int, input().split())
    e_h, e_w = map(int, input().split())

    s_h -= 1
    s_w -= 1
    e_h -= 1
    e_w -= 1

    M = []

    for i in range(H):
        s = input()
        M.append(s)

    found = False

    dq = deque()
    dist = [[True for _ in range(W)] for _ in range(H)]

    for i in range(H):
        for j in range(W):
            dist[i][j] = 1e7

    dist[s_h][s_w] = 0

    dq.append((s_h, s_w))

    while dq:
        h, w = dq.pop()
        # print(h, w)
        if h == e_h and w == e_w:
            found = True
            break
        for dx in range(-2, 3, 1):
            for dy in range(-2, 3, 1):
                nh = h + dx
                nw = w + dy
                if dx == 0 and dy == 0:
                    continue
                if nh >= H or nh < 0 or nw >= W or nw < 0:
                    continue
                d = 1
                if M[nh][nw] == '#':
                    continue
                if (abs(dx) == 1 and abs(dy) == 0) or (abs(dy) == 1 and abs(dx) == 0):
                    d = 0
                if dist[nh][nw] > dist[h][w] + d:
                    dist[nh][nw] = dist[h][w] + d
                    if d == 0:
                        dq.append((nh, nw))
                    else:
                        dq.appendleft((nh, nw))
    if not found:
        dist[e_h][e_w] = -1
    print(dist[e_h][e_w])
    # for dx in range(-2, 3, 1):
    #         for dy in range(-2, 3, 1):
    #             print(dx, dy)


Fixed submission:
from collections import deque


if __name__ == '__main__':

    H, W = map(int, input().split())
    s_h, s_w = map(int, input().split())
    e_h, e_w = map(int, input().split())

    s_h -= 1
    s_w -= 1
    e_h -= 1
    e_w -= 1

    M = []

    for i in range(H):
        s = input()
        M.append(s)

    found = False

    dq = deque()
    dist = [[0 for _ in range(W)] for _ in range(H)]

    for i in range(H):
        for j in range(W):
            dist[i][j] = int(1e7)

    dist[s_h][s_w] = 0

    dq.append((s_h, s_w))

    while dq:
        h, w = dq.pop()
        # print(h, w)
        if h == e_h and w == e_w:
            found = True
            break
        for dx in range(-2, 3, 1):
            for dy in range(-2, 3, 1):
                nh = h + dx
                nw = w + dy
                if dx == 0 and dy == 0:
                    continue
                if nh >= H or nh < 0 or nw >= W or nw < 0:
                    continue
                d = 1
                if M[nh][nw] == '#':
                    continue
                if (abs(dx) == 1 and abs(dy) == 0) or (abs(dy) == 1 and abs(dx) == 0):
                    d = 0
                if dist[nh][nw] > dist[h][w] + d:
                    dist[nh][nw] = dist[h][w] + d
                    if d == 0:
                        dq.append((nh, nw))
                    else:
                        dq.appendleft((nh, nw))
    if not found:
        dist[e_h][e_w] = -1
    print(dist[e_h][e_w])
    # for dx in range(-2, 3, 1):
    #         for dy in range(-2, 3, 1):
    #             print(dx, dy)

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

H = 0
W = 0

def within_interval(h, w):
    global H
    global W
    if 0 <= h < H and 0 <= w < W:
        return True
    return False


def find_distance(start_h, start_w, end_h, end_w, M):

    #possible moves of type A
    d_a = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    #possible moves of type B
    d_b = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
          (-1, -2), (-1, -1), (-1, 1), (-1, 2),
          (0, -2), (0, 2),
          ( 1, -2), ( 1, -1), ( 1, 1), ( 1, 2),
          ( 2, -2), ( 2, -1), ( 2, 0), ( 2, 1), ( 2, 2)]

    q1 = deque()
    q1.append((0, start_h, start_w))

    # q = PriorityQueue()
    # q.put((0, start_h, start_w))

    while q1:#not(q1.empty()):

        d, h, w = q1.pop()
        M[h][w] = True
        # print(h, w)
        #if reached the node we wanted we move
        if h == end_h and w == end_w:
            return d

        for shift in d_a:
            #check if we reached the end
            dh = h + shift[0]
            dw = w + shift[1]
            if within_interval(dh, dw) and not(M[dh][dw]):
                q1.append((d, dh, dw))
                # q.put((d, move[0], move[1]))
        for shift in d_b:
            #check if we reached the end
            dh = h + shift[0]
            dw = w + shift[1]
            if within_interval(dh, dw) and not(M[dh][dw]):
                q1.appendleft((d + 1, dh, dw))
                # q.put((d + 1, move[0], move[1]))
    return -1


if __name__ == '__main__':

    H, W = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())

    # M_ = dict()
    M = [[True for _ in range(W)] for _ in range(H)]

    for i in range(H):
        s = input()
        for j in range(len(s)):
            if s[j] == '.':
                # M_[(i,j)] = False
                M[i][j] = False

    # print(M)
    res = find_distance(c_h - 1, c_w - 1, d_h - 1, d_w - 1, M)
    print(res)

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


Fixed submission:
from collections import deque


if __name__ == '__main__':

    H, W = map(int, input().split())
    s_h, s_w = map(int, input().split())
    e_h, e_w = map(int, input().split())

    s_h -= 1
    s_w -= 1
    e_h -= 1
    e_w -= 1

    M = []

    for i in range(H):
        s = input()
        M.append(s)

    found = False

    dq = deque()
    dist = [[0 for _ in range(W)] for _ in range(H)]

    for i in range(H):
        for j in range(W):
            dist[i][j] = int(1e7)

    dist[s_h][s_w] = 0

    dq.append((s_h, s_w))

    while dq:
        h, w = dq.pop()
        # print(h, w)
        if h == e_h and w == e_w:
            found = True
            break
        for dx in range(-2, 3, 1):
            for dy in range(-2, 3, 1):
                nh = h + dx
                nw = w + dy
                if dx == 0 and dy == 0:
                    continue
                if nh >= H or nh < 0 or nw >= W or nw < 0:
                    continue
                d = 1
                if M[nh][nw] == '#':
                    continue
                if (abs(dx) == 1 and abs(dy) == 0) or (abs(dy) == 1 and abs(dx) == 0):
                    d = 0
                if dist[nh][nw] > dist[h][w] + d:
                    dist[nh][nw] = dist[h][w] + d
                    if d == 0:
                        dq.append((nh, nw))
                    else:
                        dq.appendleft((nh, nw))
    if not found:
        dist[e_h][e_w] = -1
    print(dist[e_h][e_w])
    # for dx in range(-2, 3, 1):
    #         for dy in range(-2, 3, 1):
    #             print(dx, dy)

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


def find_distance(start_h, start_w, end_h, end_w, M_):

    #possible moves of type A
    d_a = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    #possible moves of type B
    d_b = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
          (-1, -2), (-1, -1), (-1, 1), (-1, 2),
          (0, -2), (0, 2),
          ( 1, -2), ( 1, -1), ( 1, 1), ( 1, 2),
          ( 2, -2), ( 2, -1), ( 2, 0), ( 2, 1), ( 2, 2)]

    q1 = deque()
    q1.append((0, start_h, start_w))

    # q = PriorityQueue()
    # q.put((0, start_h, start_w))

    while q1:#not(q1.empty()):

        d, h, w = q1.pop()
        M_[(h, w)] = True

        #if reached the node we wanted we move
        if (h, w) == (end_h, end_w):
            return d

        for shift in d_a:
            #check if we reached the end
            move = (h + shift[0], w + shift[1])
            if move == (end_h, end_w):
                return d
            if move in M_ and not(M_[move]):
                q1.append((d, move[0], move[1]))
                # q.put((d, move[0], move[1]))
        for shift in d_b:
            #check if we reached the end
            move = (h + shift[0], w + shift[1])
            # if move == (end_h, end_w):
            #     return d + 1
            if move in M_ and not(M_[move]):
                q1.appendleft((d + 1, move[0], move[1]))
                # q.put((d + 1, move[0], move[1]))
    return -1


if __name__ == '__main__':

    H, W = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())

    M_ = dict()

    for i in range(H):
        s = input()
        for j in range(len(s)):
            if s[j] == '.':
                M_[(i,j)] = False

    res = find_distance(c_h - 1, c_w - 1, d_h - 1, d_w - 1, M_)
    print(res)


Fixed submission:
from collections import deque


if __name__ == '__main__':

    H, W = map(int, input().split())
    s_h, s_w = map(int, input().split())
    e_h, e_w = map(int, input().split())

    s_h -= 1
    s_w -= 1
    e_h -= 1
    e_w -= 1

    M = []

    for i in range(H):
        s = input()
        M.append(s)

    found = False

    dq = deque()
    dist = [[0 for _ in range(W)] for _ in range(H)]

    for i in range(H):
        for j in range(W):
            dist[i][j] = int(1e7)

    dist[s_h][s_w] = 0

    dq.append((s_h, s_w))

    while dq:
        h, w = dq.pop()
        # print(h, w)
        if h == e_h and w == e_w:
            found = True
            break
        for dx in range(-2, 3, 1):
            for dy in range(-2, 3, 1):
                nh = h + dx
                nw = w + dy
                if dx == 0 and dy == 0:
                    continue
                if nh >= H or nh < 0 or nw >= W or nw < 0:
                    continue
                d = 1
                if M[nh][nw] == '#':
                    continue
                if (abs(dx) == 1 and abs(dy) == 0) or (abs(dy) == 1 and abs(dx) == 0):
                    d = 0
                if dist[nh][nw] > dist[h][w] + d:
                    dist[nh][nw] = dist[h][w] + d
                    if d == 0:
                        dq.append((nh, nw))
                    else:
                        dq.appendleft((nh, nw))
    if not found:
        dist[e_h][e_w] = -1
    print(dist[e_h][e_w])
    # for dx in range(-2, 3, 1):
    #         for dy in range(-2, 3, 1):
    #             print(dx, dy)

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


def find_distance(start_h, start_w, end_h, end_w, M_):

    #possible moves of type A
    d_a = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    #possible moves of type B
    d_b = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
          (-1, -2), (-1, -1), (-1, 1), (-1, 2),
          (0, -2), (0, 2),
          ( 1, -2), ( 1, -1), ( 1, 1), ( 1, 2),
          ( 2, -2), ( 2, -1), ( 2, 0), ( 2, 1), ( 2, 2)]

    q1 = deque()
    q1.append((0, start_h, start_w))

    # q = PriorityQueue()
    # q.put((0, start_h, start_w))

    while q1:#not(q1.empty()):

        d, h, w = q1.pop()
        M_[(h, w)] = True

        #if reached the node we wanted we move
        if (h, w) == (end_h, end_w):
            return d

        for shift in d_a:
            #check if we reached the end
            move = (h + shift[0], w + shift[1])
            # if move == (end_h, end_w):
            #     return d
            if move in M_ and not(M_[move]):
                q1.append((d, move[0], move[1]))
                # q.put((d, move[0], move[1]))
        for shift in d_b:
            #check if we reached the end
            move = (h + shift[0], w + shift[1])
            # if move == (end_h, end_w):
            #     return d + 1
            if move in M_ and not(M_[move]):
                q1.appendleft((d + 1, move[0], move[1]))
                # q.put((d + 1, move[0], move[1]))
    return -1


if __name__ == '__main__':

    H, W = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())

    M_ = dict()

    for i in range(H):
        s = input()
        for j in range(len(s)):
            if s[j] == '.':
                M_[(i,j)] = False

    res = find_distance(c_h - 1, c_w - 1, d_h - 1, d_w - 1, M_)
    print(res)

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


Fixed submission:
from collections import deque


if __name__ == '__main__':

    H, W = map(int, input().split())
    s_h, s_w = map(int, input().split())
    e_h, e_w = map(int, input().split())

    s_h -= 1
    s_w -= 1
    e_h -= 1
    e_w -= 1

    M = []

    for i in range(H):
        s = input()
        M.append(s)

    found = False

    dq = deque()
    dist = [[0 for _ in range(W)] for _ in range(H)]

    for i in range(H):
        for j in range(W):
            dist[i][j] = int(1e7)

    dist[s_h][s_w] = 0

    dq.append((s_h, s_w))

    while dq:
        h, w = dq.pop()
        # print(h, w)
        if h == e_h and w == e_w:
            found = True
            break
        for dx in range(-2, 3, 1):
            for dy in range(-2, 3, 1):
                nh = h + dx
                nw = w + dy
                if dx == 0 and dy == 0:
                    continue
                if nh >= H or nh < 0 or nw >= W or nw < 0:
                    continue
                d = 1
                if M[nh][nw] == '#':
                    continue
                if (abs(dx) == 1 and abs(dy) == 0) or (abs(dy) == 1 and abs(dx) == 0):
                    d = 0
                if dist[nh][nw] > dist[h][w] + d:
                    dist[nh][nw] = dist[h][w] + d
                    if d == 0:
                        dq.append((nh, nw))
                    else:
                        dq.appendleft((nh, nw))
    if not found:
        dist[e_h][e_w] = -1
    print(dist[e_h][e_w])
    # for dx in range(-2, 3, 1):
    #         for dy in range(-2, 3, 1):
    #             print(dx, dy)

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


def find_distance(start_h, start_w, end_h, end_w, M_):

    #possible moves of type A
    d_a = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    #possible moves of type B
    d_b = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
          (-1, -2), (-1, -1), (-1, 1), (-1, 2),
          (0, -2), (0, 2),
          ( 1, -2), ( 1, -1), ( 1, 1), ( 1, 2),
          ( 2, -2), ( 2, -1), ( 2, 0), ( 2, 1), ( 2, 2)]

    # q = deque()
    q = PriorityQueue()
    q.put((0, start_h, start_w))

    while not(q.empty()):
        d, h, w = q.get()
        M_[(h, w)] = True

        #if reached the node we wanted we move
        if (h, w) == (end_h, end_w):
            return d

        for shift in d_a:
            #check if we reached the end
            move = (h + shift[0], w + shift[1])
            # if move == (end_h, end_w):
            #     return d
            if move in M_ and not(M_[move]):
                q.put((d, move[0], move[1]))
        for shift in d_b:
            #check if we reached the end
            move = (h + shift[0], w + shift[1])
            # if move == (end_h, end_w):
            #     return d + 1
            if move in M_ and not(M_[move]):
                q.put((d + 1, move[0], move[1]))
    return -1


if __name__ == '__main__':

    H, W = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())

    M_ = dict()

    for i in range(H):
        s = input()
        for j in range(len(s)):
            if s[j] == '.':
                M_[(i,j)] = False

    res = find_distance(c_h - 1, c_w - 1, d_h - 1, d_w - 1, M_)
    print(res)


Fixed submission:
from collections import deque


if __name__ == '__main__':

    H, W = map(int, input().split())
    s_h, s_w = map(int, input().split())
    e_h, e_w = map(int, input().split())

    s_h -= 1
    s_w -= 1
    e_h -= 1
    e_w -= 1

    M = []

    for i in range(H):
        s = input()
        M.append(s)

    found = False

    dq = deque()
    dist = [[0 for _ in range(W)] for _ in range(H)]

    for i in range(H):
        for j in range(W):
            dist[i][j] = int(1e7)

    dist[s_h][s_w] = 0

    dq.append((s_h, s_w))

    while dq:
        h, w = dq.pop()
        # print(h, w)
        if h == e_h and w == e_w:
            found = True
            break
        for dx in range(-2, 3, 1):
            for dy in range(-2, 3, 1):
                nh = h + dx
                nw = w + dy
                if dx == 0 and dy == 0:
                    continue
                if nh >= H or nh < 0 or nw >= W or nw < 0:
                    continue
                d = 1
                if M[nh][nw] == '#':
                    continue
                if (abs(dx) == 1 and abs(dy) == 0) or (abs(dy) == 1 and abs(dx) == 0):
                    d = 0
                if dist[nh][nw] > dist[h][w] + d:
                    dist[nh][nw] = dist[h][w] + d
                    if d == 0:
                        dq.append((nh, nw))
                    else:
                        dq.appendleft((nh, nw))
    if not found:
        dist[e_h][e_w] = -1
    print(dist[e_h][e_w])
    # for dx in range(-2, 3, 1):
    #         for dy in range(-2, 3, 1):
    #             print(dx, dy)