Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
import heapq
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

def main():
    from builtins import int, map
    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)]

    dist = defaultdict(lambda: float("inf"))
    queue = deque([(Ch, Cw, 0)])

    while queue:
        (h, w, d) = queue.popleft()

        if dist[h, w] == float("inf") or dist[h, w] > d:
            dist[h, w] = d
            
            # 5x5-grid
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nh, nw = h + ddh, w + ddw
                    if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                        # cost-0 move
                        if abs(ddh) + abs(ddw) <= 1:
                            queue.appendleft((nh, nw, d))
                        # cost-1 move
                        else:
                            queue.append((nh, nw, d + 1))

    if dist[Dh, Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh, Dw])

if __name__ == '__main__':
    main()


Fixed submission:
from collections import deque
INF = int(1e10)

def main():
    from builtins import int, map
    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)]

    # dist = defaultdict(lambda: float("inf"))
    dist = [[float("inf")] * W for _ in range(H)]
    queue = deque([(Ch, Cw, 0)])

    while queue:
        (h, w, d) = queue.popleft()

        if dist[h][w] == float("inf") or dist[h][w] > d:
            dist[h][w] = d
            
            # 5x5-grid
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nh, nw = h + ddh, w + ddw
                    if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                        # cost-0 move
                        if abs(ddh) + abs(ddw) <= 1:
                            queue.appendleft((nh, nw, d))
                        # cost-1 move
                        else:
                            queue.append((nh, nw, d + 1))

    if dist[Dh][Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh][Dw])

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
import heapq
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]

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

    dist = defaultdict(lambda: float("inf"))
    dist[Ch, Cw] = 0
    queue = deque([(Ch, Cw)])

    while queue:
        (h, w) = queue.popleft()

        for i in range(4):
            dhi, dwi = dh[i], dw[i]
            nh, nw = h + dhi, w + dwi
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                if dist[h, w] < dist[nh, nw] :
                    dist[nh, nw] = dist[h, w]
                    queue.appendleft((nh, nw))
        
        # 5x5-grid
        for ddh in range(-2, 3):
            for ddw in range(-2, 3):
                if abs(ddh) + abs(ddw) <= 1:
                    continue
                nh, nw = h + ddh, w + ddw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                    if dist[nh, nw] > dist[h, w] + 1:
                        dist[nh, nw] = dist[h, w] + 1
                        queue.append((nh, nw))

    if dist[Dh, Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh, Dw])

if __name__ == '__main__':
    main()


Fixed submission:
from collections import deque
INF = int(1e10)

def main():
    from builtins import int, map
    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)]

    # dist = defaultdict(lambda: float("inf"))
    dist = [[float("inf")] * W for _ in range(H)]
    queue = deque([(Ch, Cw, 0)])

    while queue:
        (h, w, d) = queue.popleft()

        if dist[h][w] == float("inf") or dist[h][w] > d:
            dist[h][w] = d
            
            # 5x5-grid
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nh, nw = h + ddh, w + ddw
                    if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                        # cost-0 move
                        if abs(ddh) + abs(ddw) <= 1:
                            queue.appendleft((nh, nw, d))
                        # cost-1 move
                        else:
                            queue.append((nh, nw, d + 1))

    if dist[Dh][Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh][Dw])

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
import heapq
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]

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

    dist = defaultdict(lambda: float("inf"))
    dist[Ch, Cw] = 0
    queue = deque([(Ch, Cw)])

    while queue:
        (h, w) = queue.popleft()

        for i in range(4):
            dhi, dwi = dh[i], dw[i]
            nh, nw = h + dhi, w + dwi
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                if dist[h, w] < dist[nh, nw] :
                    dist[nh, nw] = dist[h, w]
                    queue.appendleft((nh, nw))
        
        # 5x5-grid
        for ddh in range(-2, 3):
            for ddw in range(-2, 3):
                nh, nw = h + ddh, w + ddw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                    if dist[nh, nw] > dist[h, w] + 1:
                        dist[nh, nw] = dist[h, w] + 1
                        queue.append((nh, nw))

    if dist[Dh, Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh, Dw])

if __name__ == '__main__':
    main()


Fixed submission:
from collections import deque
INF = int(1e10)

def main():
    from builtins import int, map
    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)]

    # dist = defaultdict(lambda: float("inf"))
    dist = [[float("inf")] * W for _ in range(H)]
    queue = deque([(Ch, Cw, 0)])

    while queue:
        (h, w, d) = queue.popleft()

        if dist[h][w] == float("inf") or dist[h][w] > d:
            dist[h][w] = d
            
            # 5x5-grid
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nh, nw = h + ddh, w + ddw
                    if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                        # cost-0 move
                        if abs(ddh) + abs(ddw) <= 1:
                            queue.appendleft((nh, nw, d))
                        # cost-1 move
                        else:
                            queue.append((nh, nw, d + 1))

    if dist[Dh][Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh][Dw])

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
import heapq
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]

def main():
    from builtins import int, map
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Ch, Cw = Ch - 1, Cw - 1
    Dh, Dw = Dh - 1, Dw - 1
    S = [list(input()) for _ in range(H)]
    counter = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                counter += 1
    # for row in S: print(*row)

    # DFSする (近隣への移動はコスト0，ワープ(5x5-grid)はコスト1)
    dist = defaultdict(lambda: float("inf"))
    dist[Ch, Cw] = 0
    queue = deque([(Ch, Cw, 0)])

    while queue:
        (h, w, d) = queue.popleft()

        if (h, w) == (Dh, Dw):
            break

        for i in range(4):
            dhi, dwi = dh[i], dw[i]
            nh, nw = h + dhi, w + dwi
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                if dist[nh, nw] == float("inf") or dist[nh, nw] > d:
                    dist[nh, nw] = dist[h, w]
                    queue.appendleft((nh, nw, d))
        
        # 5x5-grid
        for ddh in range(-2, 3):
            for ddw in range(-2, 3):
                nh, nw = h + ddh, w + ddw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                    if dist[nh, nw] == float("inf"):
                        if dist[nh, nw] > dist[h, w] + 1:
                            dist[nh, nw] = dist[h, w] + 1
                            queue.append((nh, nw, d + 1))

    if dist[Dh, Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh, Dw])

if __name__ == '__main__':
    main()


Fixed submission:
from collections import deque
INF = int(1e10)

def main():
    from builtins import int, map
    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)]

    # dist = defaultdict(lambda: float("inf"))
    dist = [[float("inf")] * W for _ in range(H)]
    queue = deque([(Ch, Cw, 0)])

    while queue:
        (h, w, d) = queue.popleft()

        if dist[h][w] == float("inf") or dist[h][w] > d:
            dist[h][w] = d
            
            # 5x5-grid
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nh, nw = h + ddh, w + ddw
                    if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                        # cost-0 move
                        if abs(ddh) + abs(ddw) <= 1:
                            queue.appendleft((nh, nw, d))
                        # cost-1 move
                        else:
                            queue.append((nh, nw, d + 1))

    if dist[Dh][Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh][Dw])

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
import heapq
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]

def main():
    from builtins import int, map
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Ch, Cw = Ch - 1, Cw - 1
    Dh, Dw = Dh - 1, Dw - 1
    S = [list(input()) for _ in range(H)]
    counter = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                counter += 1
    # for row in S: print(*row)

    # DFSする (近隣への移動はコスト0，ワープ(5x5-grid)はコスト1)
    dist = defaultdict(lambda: float("inf"))
    dist[Ch, Cw] = 0
    queue = deque([(Ch, Cw)])

    while queue:
        (h, w) = queue.popleft()

        if (h, w) == (Dh, Dw):
            break

        for i in range(4):
            dhi, dwi = dh[i], dw[i]
            nh, nw = h + dhi, w + dwi
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                if dist[nh, nw] == float("inf") or dist[nh, nw] > dist[h, w]:
                    dist[nh, nw] = dist[h, w]
                    queue.appendleft((nh, nw))
        
        # 5x5-grid
        for ddh in range(-2, 3):
            for ddw in range(-2, 3):
                nh, nw = h + ddh, w + ddw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                    if dist[nh, nw] == float("inf"):
                        if dist[nh, nw] > dist[h, w] + 1:
                            dist[nh, nw] = dist[h, w] + 1
                            queue.append((nh, nw))

    if dist[Dh, Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh, Dw])

if __name__ == '__main__':
    main()


Fixed submission:
from collections import deque
INF = int(1e10)

def main():
    from builtins import int, map
    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)]

    # dist = defaultdict(lambda: float("inf"))
    dist = [[float("inf")] * W for _ in range(H)]
    queue = deque([(Ch, Cw, 0)])

    while queue:
        (h, w, d) = queue.popleft()

        if dist[h][w] == float("inf") or dist[h][w] > d:
            dist[h][w] = d
            
            # 5x5-grid
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nh, nw = h + ddh, w + ddw
                    if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                        # cost-0 move
                        if abs(ddh) + abs(ddw) <= 1:
                            queue.appendleft((nh, nw, d))
                        # cost-1 move
                        else:
                            queue.append((nh, nw, d + 1))

    if dist[Dh][Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh][Dw])

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
import heapq
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]

def main():
    from builtins import int, map
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Ch, Cw = Ch - 1, Cw - 1
    Dh, Dw = Dh - 1, Dw - 1
    S = [list(input()) for _ in range(H)]
    counter = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                counter += 1
    # for row in S: print(*row)

    # DFSする (近隣への移動はコスト0，ワープ(5x5-grid)はコスト1)
    dist = defaultdict(lambda: float("inf"))
    dist[Ch, Cw] = 0

    while True:
        visited = set({(Ch, Cw)})
        queue = []
        heapq.heappush(queue, (0, (Ch, Cw)))
        while queue:
            d, (h, w) = heapq.heappop(queue)
            if dist[h, w] < d:
                continue
            
            dist[h, w] = d
            visited.add((h, w))
            # print(queue)

            if dist[h, w] < d:
                continue

            if (h, w) == (Dh, Dw):
                break

            for i in range(4):
                dhi, dwi = dh[i], dw[i]
                nh, nw = h + dhi, w + dwi
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                    if (nh, nw) not in visited:
                        nd = d + 0
                        heapq.heappush(queue, (nd, (nh, nw)))
            
            # 5x5-grid
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nnh, nnw = h + ddh, w + ddw
                    if 0 <= nnh < H and 0 <= nnw < W and S[nnh][nnw] != '#':
                        if (nnh, nnw) not in visited:
                            nd = d + 1
                            heapq.heappush(queue, (nd, (nnh, nnw)))

        break

    if dist[Dh, Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh, Dw])

if __name__ == '__main__':
    main()


Fixed submission:
from collections import deque
INF = int(1e10)

def main():
    from builtins import int, map
    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)]

    # dist = defaultdict(lambda: float("inf"))
    dist = [[float("inf")] * W for _ in range(H)]
    queue = deque([(Ch, Cw, 0)])

    while queue:
        (h, w, d) = queue.popleft()

        if dist[h][w] == float("inf") or dist[h][w] > d:
            dist[h][w] = d
            
            # 5x5-grid
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nh, nw = h + ddh, w + ddw
                    if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                        # cost-0 move
                        if abs(ddh) + abs(ddw) <= 1:
                            queue.appendleft((nh, nw, d))
                        # cost-1 move
                        else:
                            queue.append((nh, nw, d + 1))

    if dist[Dh][Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh][Dw])

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
from heapq import heapify, heappush, heappop
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]

class UnionFind(object):
    def __init__(self, n):
        self.n = n
        self.par = [-1] * n
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return False
        else:
            if self.par[x] > self.par[y]:
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x
            return True

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

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

    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.par) if x < 0]

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

dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]

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

    ncon_num = 0
    nodes = []
    idx = {}
    groups = {}
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                idx[(h, w)] = len(nodes)
                groups[h, w] = None
                nodes.append((h, w))
    N = len(nodes)
    uf = UnionFind(N)

    for h in range(H):
        for w in range(W):
            if S[h][w] == '#': continue
            I = idx[h, w]
            for i in range(4):
                nnh, nnw = h + dh[i], w + dw[i]
                if 0 <= nnh < H and 0 <= nnw < W and S[nnh][nnw] != '#':
                    J = idx[nnh, nnw]
                    uf.unite(I, J)

    for h in range(H):
        for w in range(W):
            if S[h][w] == '#': continue
            I = idx[h, w]
            # print(I, uf.members(I))
            if groups[nodes[I]] is None:
                groups[nodes[I]] = ncon_num
                for k in uf.members(I):
                    groups[nodes[k]] = ncon_num
                ncon_num += 1

    if ncon_num == 1:
        print(0)
        exit()

    ncon = len(set(groups.values()))
    start_con, goal_con = groups[Ch, Cw], groups[Dh, Dw]
    # print(ncon, start_con, goal_con)
    # print(groups)
    
    dist_mat = [[float("inf")] * ncon for _ in range(ncon)]
    for k in range(ncon):
        dist_mat[k][k] = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#': continue
            I = idx[h, w]
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nnh, nnw = h + ddh, w + ddw
                    if 0 <= nnh < H and 0 <= nnw < W and S[nnh][nnw] != '#':
                        J = idx[nnh, nnw]
                        if I != J:
                            # print(I, J, groups[nodes[I]], groups[nodes[J]], uf.same(I, J))
                            if not uf.same(I, J):
                                di = groups[nodes[I]]
                                dj = groups[nodes[J]]
                                dist_mat[di][dj] = 1

    # 作成したグラフでDijkstra
    dist = [float("inf")] * ncon
    dist[start_con] = 0
    queue = [(0, start_con)]
    while queue:
        dc, c = heappop(queue)
        if dist[c] < dc:
            continue

        for cc in range(ncon):
            cost = dist_mat[c][cc]
            if dist != float("inf") and dist[cc] > dist[c] + cost:
                dist[cc] = dist[c] + cost
                heappush(queue, (dist[cc], cc))

    if dist[goal_con] == float("inf"):
        print(-1)
    else:
        print(dist[goal_con])


if __name__ == '__main__':
    main()


Fixed submission:
from collections import deque
INF = int(1e10)

def main():
    from builtins import int, map
    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)]

    # dist = defaultdict(lambda: float("inf"))
    dist = [[float("inf")] * W for _ in range(H)]
    queue = deque([(Ch, Cw, 0)])

    while queue:
        (h, w, d) = queue.popleft()

        if dist[h][w] == float("inf") or dist[h][w] > d:
            dist[h][w] = d
            
            # 5x5-grid
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nh, nw = h + ddh, w + ddw
                    if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                        # cost-0 move
                        if abs(ddh) + abs(ddw) <= 1:
                            queue.appendleft((nh, nw, d))
                        # cost-1 move
                        else:
                            queue.append((nh, nw, d + 1))

    if dist[Dh][Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh][Dw])

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
from heapq import heapify, heappush, heappop
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]

def main():
    from builtins import int, map
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Ch, Cw = Ch - 1, Cw - 1
    Dh, Dw = Dh - 1, Dw - 1
    S = [list(input()) for _ in range(H)]
    counter = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                counter += 1
    # for row in S: print(*row)

    # 連結成分を調べる
    num_con = {}
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                num_con[h, w] = None

    ncon_num = 0
    for h in range(H):
        for w in range(W):
            # 既に決まっていたらいらない
            if S[h][w] != '.' or num_con[h, w] != None:
                continue
            num_con[h, w] = ncon_num
            dist = defaultdict(lambda: float("inf"))
            dist[h, w] = 0
            queue = []
            heappush(queue, (0, (h, w)))
            visited = set({})

            while queue:
                d, (nh, nw) = heappop(queue)
                dist[nh, nw] = d
                num_con[nh, nw] = ncon_num
                visited.add((nh, nw))

                if dist[nh, nw] < d:
                    continue

                for i in range(4):
                    dhi, dwi = dh[i], dw[i]
                    nnh, nnw = nh + dhi, nw + dwi
                    if 0 <= nnh < H and 0 <= nnw < W and S[nnh][nnw] != '#':
                        if num_con[nnh, nnw] is None:
                            # if (nnh, nnw) not in visited:
                            heappush(queue, (d, (nnh, nnw)))

            # 次
            ncon_num += 1

    if ncon_num == 1:
        print(0)
        exit()
            
    con_nodes = defaultdict(set)
    start_con = None
    goal_con = None
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                con_nodes[num_con[h, w]].add((h, w))
                if (h, w) == (Ch, Cw):
                    start_con = num_con[h, w]
                if (h, w) == (Dh, Dw):
                    goal_con = num_con[h, w]
    ncon = len(con_nodes)

    # pair-wiseに調べる
    # print(ncon, start_con, goal_con)
    dist_mat = [[float("inf")] * ncon for _ in range(ncon)]
    for g1 in range(ncon):
        for g2 in range(ncon):
            if g1 == g2:
                dist_mat[g1][g2] = dist_mat[g2][g1] = 0
            else:
                flag = False
                for (h1, w1) in con_nodes[g1]:
                    for (h2, w2) in con_nodes[g2]:
                        ddh = abs(h1 - h2)
                        ddw = abs(w1 - w2)
                        if ddh <= 2 and ddw <= 2:
                            flag = True
                            break
                    if flag:
                        break
                if flag:
                    dist_mat[g1][g2] = dist_mat[g2][g1] = 1

    # for dd in dist_mat: print(*dd)

    # 作成したグラフでDijkstra
    dist = [float("inf")] * ncon
    dist[start_con] = 0
    queue = [(0, start_con)]
    while queue:
        dc, c = heappop(queue)
        if dist[c] < dc:
            continue

        for cc in range(ncon):
            cost = dist_mat[c][cc]
            if dist != float("inf") and dist[cc] > dist[c] + cost:
                dist[cc] = dist[c] + cost
                heappush(queue, (dist[cc], cc))

    if dist[goal_con] == float("inf"):
        print(-1)
    else:
        print(dist[goal_con])


if __name__ == '__main__':
    main()


Fixed submission:
from collections import deque
INF = int(1e10)

def main():
    from builtins import int, map
    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)]

    # dist = defaultdict(lambda: float("inf"))
    dist = [[float("inf")] * W for _ in range(H)]
    queue = deque([(Ch, Cw, 0)])

    while queue:
        (h, w, d) = queue.popleft()

        if dist[h][w] == float("inf") or dist[h][w] > d:
            dist[h][w] = d
            
            # 5x5-grid
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nh, nw = h + ddh, w + ddw
                    if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                        # cost-0 move
                        if abs(ddh) + abs(ddw) <= 1:
                            queue.appendleft((nh, nw, d))
                        # cost-1 move
                        else:
                            queue.append((nh, nw, d + 1))

    if dist[Dh][Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh][Dw])

if __name__ == '__main__':
    main()