Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
INF = 10**10
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
mat = []
for _ in range(h):
    s = input()
    mat.append(s)

costs = [[INF for _ in range(w)] for _ in range(h)]
costs[ch-1][cw-1] = 0
queue = deque()
queue.append((ch-1, cw-1))
while len(queue) > 0:
    x, y = queue.popleft()
    for i in range(4):
        dx = [-1, 0, 1, 0][i]
        dy = [0, -1, 0, 1][i]
        nx = x+dx
        ny = y+dy
        if nx < 0 or h <= nx or ny < 0 or w <= ny:
            continue
        if mat[nx][ny] == "#":
            continue
        if costs[nx][ny] > costs[x][y]:
            costs[nx][ny] = costs[x][y]
            queue.appendleft((nx, ny))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx = x+i
            ny = y+j
            if nx < 0 or h <= nx or ny < 0 or w <= ny:
                continue
            if mat[nx][ny] == "#":
                continue
            if costs[nx][ny] > costs[x][y] + 1:
                costs[nx][ny] = costs[x][y] + 1
                queue.append((nx, ny))
if costs[dh-1][dw-1] == INF:
    print(-1)
else:
    print(costs[dh-1][dw-1])



Fixed submission:
from collections import deque
INF = 10**10
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
mat = []
for _ in range(h):
    s = input()
    mat.append(s)

costs = [[INF for _ in range(w)] for _ in range(h)]
costs[ch-1][cw-1] = 0
queue = deque()
queue.append((ch-1, cw-1))
while len(queue) > 0:
    x, y = queue.popleft()
    for i in range(4):
        dx = [-1, 0, 1, 0][i]
        dy = [0, -1, 0, 1][i]
        nx = x+dx
        ny = y+dy
        if nx < 0 or h <= nx or ny < 0 or w <= ny:
            continue
        if mat[nx][ny] == "#":
            continue
        if costs[nx][ny] > costs[x][y]:
            costs[nx][ny] = costs[x][y]
            queue.appendleft((nx, ny))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx = x+i
            ny = y+j
            if nx < 0 or h <= nx or ny < 0 or w <= ny:
                continue
            if mat[nx][ny] == "#":
                continue
            if costs[nx][ny] > costs[x][y] + 1:
                costs[nx][ny] = costs[x][y] + 1
                queue.append((nx, ny))
if costs[dh-1][dw-1] == INF:
    print(-1)
else:
    print(costs[dh-1][dw-1])

Buggy python submission (verdict: Time Limit Exceeded):
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def to_idx(x, y):
    return w*x+y
def from_idx(idx):
    return (idx//w, idx-idx//w*w)

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
mat = []
for _ in range(h):
    s = input()
    mat.append(s)

union_find = UnionFind(h*w)
for i in range(h):
    for j in range(w):
        c = mat[i][j]
        if c == "#":
            continue
        for d_id in range(4):
            dx = [-1, 0, 1, 0][d_id]
            dy = [0, 1, 0, -1][d_id]
            if i + dx < 0 or h <= i + dx or j + dy < 0 or w <= j + dy:
                continue
            dc = mat[i+dx][j+dy]
            if dc == ".":
                union_find.union(to_idx(i, j), to_idx(i+dx, j+dy))
roots = [i for i in union_find.roots() if mat[from_idx(i)[0]][from_idx(i)[1]] == "."]
root_dict = {v: i for i, v in enumerate(roots)}

island_num = len(root_dict.keys())
warp_mat = [[0 for _ in range(island_num)] for _ in range(island_num)]
for i in range(h):
    for j in range(w):
        c = mat[i][j]
        c_idx = to_idx(i, j)
        if c == "#":
            continue
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if i + dx < 0 or h <= i + dx or j + dy < 0 or w <= j + dy:
                    continue
                dc = mat[i+dx][j+dy]
                dc_idx = to_idx(i+dx, j+dy)
                if dc == "#":
                    continue
                if union_find.find(c_idx) != union_find.find(dc_idx):
                    c_root_idx = root_dict[union_find.find(c_idx)]
                    dc_root_idx = root_dict[union_find.find(dc_idx)]
                    warp_mat[c_root_idx][dc_root_idx] = 1
                    warp_mat[dc_root_idx][c_root_idx] = 1
start = root_dict[union_find.find(to_idx(ch-1, cw-1))]
goal = root_dict[union_find.find(to_idx(dh-1, dw-1))]

def dfs(c, g, cost, reached):
    if c == g:
        print(cost)
        exit()
    reached[c] = True
    for i, v in enumerate(warp_mat[c]):
        if v == 1 and not reached[i]:
            dfs(i, g, cost+1, reached[::])

dfs(start, goal, 0, [False for _ in range(island_num)])
print(-1)


Fixed submission:
from collections import deque
INF = 10**10
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
mat = []
for _ in range(h):
    s = input()
    mat.append(s)

costs = [[INF for _ in range(w)] for _ in range(h)]
costs[ch-1][cw-1] = 0
queue = deque()
queue.append((ch-1, cw-1))
while len(queue) > 0:
    x, y = queue.popleft()
    for i in range(4):
        dx = [-1, 0, 1, 0][i]
        dy = [0, -1, 0, 1][i]
        nx = x+dx
        ny = y+dy
        if nx < 0 or h <= nx or ny < 0 or w <= ny:
            continue
        if mat[nx][ny] == "#":
            continue
        if costs[nx][ny] > costs[x][y]:
            costs[nx][ny] = costs[x][y]
            queue.appendleft((nx, ny))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx = x+i
            ny = y+j
            if nx < 0 or h <= nx or ny < 0 or w <= ny:
                continue
            if mat[nx][ny] == "#":
                continue
            if costs[nx][ny] > costs[x][y] + 1:
                costs[nx][ny] = costs[x][y] + 1
                queue.append((nx, ny))
if costs[dh-1][dw-1] == INF:
    print(-1)
else:
    print(costs[dh-1][dw-1])