Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
def solve():
    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())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' or V[h][w] != -1:
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    # s = V[Ch][Cw]
    # g = V[Dh][Dw]

    # dist = [-1 for _ in range(vertex)]
    # que = deque()
    # dist[s] = 0
    # que.append(s)
    # while que:
    #     u = que.popleft()
    #     for v in G[u]:
    #         if dist[v] != -1:
    #             continue
    #         dist[v] = dist[u] + 1
    #         que.append(v)
    
    # print(dist[g])

    start_area_num = int(V[Ch][Cw])
    goal_area_num = int(V[Dh][Dw])

    visited = [False] * vertex

    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        visited[cur_area_num] = True
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                q.append((next_area_num, warp_cnt+1))
    else:
        print(-1)

if __name__ == '__main__':
    solve()


Fixed submission:
from collections import deque
def solve():
    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())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' or V[h][w] != -1:
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    s = V[Ch][Cw]
    g = V[Dh][Dw]

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)
    
    print(dist[g])

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
def solve():
    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())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' or V[h][w] != -1:
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    # s = V[Ch][Cw]
    # g = V[Dh][Dw]

    # dist = [-1 for _ in range(vertex)]
    # que = deque()
    # dist[s] = 0
    # que.append(s)
    # while que:
    #     u = que.popleft()
    #     for v in G[u]:
    #         if dist[v] != -1:
    #             continue
    #         dist[v] = dist[u] + 1
    #         que.append(v)
    
    # print(dist[g])

    start_area_num = V[Ch][Cw]
    goal_area_num = V[Dh][Dw]

    visited = [False] * vertex
    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        visited[cur_area_num] = True
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                q.append((next_area_num,warp_cnt+1))
    else:
        print(-1)

if __name__ == '__main__':
    solve()


Fixed submission:
from collections import deque
def solve():
    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())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' or V[h][w] != -1:
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    s = V[Ch][Cw]
    g = V[Dh][Dw]

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)
    
    print(dist[g])

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
def solve():
    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())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] != -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' or V[h][w] != -1:
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    s = V[Ch][Cw]
    g = V[Dh][Dw]

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)
    
    print(dist[g])

if __name__ == '__main__':
    solve()


Fixed submission:
from collections import deque
def solve():
    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())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' or V[h][w] != -1:
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    s = V[Ch][Cw]
    g = V[Dh][Dw]

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)
    
    print(dist[g])

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict, deque
def solve():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch -= 1
    Cw -= 1
    Dh,Dw = map(int,input().split())
    Dh -= 1
    Dw -= 1

    S = [list(input()) for _ in range(H)]
    area_num = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                bfs(h,w,H,W,S,area_num)
                area_num += 1
    
    start_area_num = int(S[Ch][Cw])
    goal_area_num = int(S[Dh][Dw])

    G = defaultdict(set)

    for h in range(H):
        for w in range(W):
            from_area_num = S[h][w]
            if from_area_num == '#':
                continue
            from_area_num = int(from_area_num)

            for dh in range(-2,2+1):
                if h+dh < 0 or h+dh >= H:
                    continue
                for dw in range(-2, 2+1):
                    if w+dw < 0 or w+dw >= W:
                        continue
                    to_area_num = S[h+dh][w+dw]
                    if to_area_num == '#':
                        continue
                    to_area_num = int(to_area_num)
                    if from_area_num != to_area_num:
                        G[to_area_num].add(from_area_num)
                        G[from_area_num].add(to_area_num)
    
    area_num_count = area_num + 1
    visited = [False] * area_num_count
    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        visited[cur_area_num] = True
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                q.append((next_area_num,warp_cnt+1))
    else:
        print(-1)

def bfs(h,w,H,W,S,area_num):
    q = deque()
    d = ((0,1),(0,-1),(1,0),(-1,0))
    q.append((h,w))
    S[h][w] = area_num
    while len(q) > 0:
        now_h, now_w = q.popleft()

        for dh, dw in d:
            if 0 <= now_h + dh < H and 0 <= now_w + dw < W and S[now_h+dh][now_w+dw] == '.':
                q.append((now_h+dh, now_w+dw))
                S[now_h+dh][now_w+dw] = area_num


if __name__ == '__main__':
    solve()


Fixed submission:
from collections import deque
def solve():
    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())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' or V[h][w] != -1:
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    s = V[Ch][Cw]
    g = V[Dh][Dw]

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)
    
    print(dist[g])

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque, defaultdict
def solve():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch -= 1
    Cw -= 1
    Dh,Dw = map(int,input().split())
    Dh -= 1
    Dw -= 1

    S = [list(input()) for _ in range(H)]
    area_num = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                dfs(h,w,H,W,S,area_num)
                area_num += 1

    start_area_num = int(S[Ch][Cw])
    goal_area_num = int(S[Dh][Dw])

    area_num_count = area_num + 1

    # G = [set() for _ in range(area_num_count)]

    # for h in range(H):
    #     for w in range(W):
    #         from_area_num = S[h][w]
    #         if from_area_num == '#':
    #             continue
    #         from_area_num = int(from_area_num)

    #         for dh in range(2+1):
    #             if h+dh < 0 or h+dh >= H:
    #                 continue
    #             for dw in range(-2,2+1):
    #                 if w+dw < 0 or w+dw >= W:
    #                     continue
    #                 to_area_num = S[h+dh][w+dw]
    #                 if to_area_num == '#':
    #                     continue
    #                 to_area_num = int(to_area_num)
    #                 if from_area_num != to_area_num:
    #                     G[to_area_num].add(from_area_num)
    #                     G[from_area_num].add(to_area_num)

    # G = [[] for _ in range(area_num_count)]
    G = defaultdict(set)
    used = [set() for _ in range(area_num_count)]
    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                continue
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if S[h+dh][w+dw] == "#":
                        continue
                    if S[h][w] == S[h+dh][w+dw]:
                        continue
                    if S[h+dh][w+dw] in used[int(S[h][w])]:
                        continue
                    G[int(S[h][w])].add((int(S[h+dh][w+dw])))
                    used[int(S[h][w])].add((S[h+dh][w+dw]))
    
    visited = [False] * area_num_count
    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        visited[cur_area_num] = True
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                q.append((next_area_num,warp_cnt+1))
    else:
        print(-1)

def dfs(h,w,H,W,S,area_num):
    if 0 <= h < H and 0 <= w < W and S[h][w] == '.':
        S[h][w] = str(area_num)
        dfs(h+1,w,H,W,S,area_num)
        dfs(h,w+1,H,W,S,area_num)
        dfs(h-1,w,H,W,S,area_num)
        dfs(h,w-1,H,W,S,area_num)

if __name__ == '__main__':
    solve()

Fixed submission:
from collections import deque
def solve():
    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())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' or V[h][w] != -1:
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    s = V[Ch][Cw]
    g = V[Dh][Dw]

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)
    
    print(dist[g])

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
def solve():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch -= 1
    Cw -= 1
    Dh,Dw = map(int,input().split())
    Dh -= 1
    Dw -= 1

    S = [list(input()) for _ in range(H)]
    area_num = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                dfs(h,w,H,W,S,area_num)
                area_num += 1

    start_area_num = int(S[Ch][Cw])
    goal_area_num = int(S[Dh][Dw])

    area_num_count = area_num + 1

    G = [set() for _ in range(area_num_count)]

    for h in range(H):
        for w in range(W):
            from_area_num = S[h][w]
            if from_area_num == '#':
                continue
            from_area_num = int(from_area_num)

            for dh in range(2+1):
                if h+dh < 0 or h+dh >= H:
                    continue
                for dw in range(-2,2+1):
                    if w+dw < 0 or w+dw >= W:
                        continue
                    to_area_num = S[h+dh][w+dw]
                    if to_area_num == '#':
                        continue
                    to_area_num = int(to_area_num)
                    if from_area_num != to_area_num:
                        G[to_area_num].add(from_area_num)
                        G[from_area_num].add(to_area_num)
    
    visited = [False] * area_num_count
    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        visited[cur_area_num] = True
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                q.append((next_area_num,warp_cnt+1))
    else:
        print(-1)

def dfs(h,w,H,W,S,area_num):
    if 0 <= h < H and 0 <= w < W and S[h][w] == '.':
        S[h][w] = str(area_num)
        dfs(h+1,w,H,W,S,area_num)
        dfs(h,w+1,H,W,S,area_num)
        dfs(h-1,w,H,W,S,area_num)
        dfs(h,w-1,H,W,S,area_num)

def mod_graph(G,including_area_num_set):
    for area_num_from in including_area_num_set:
        for area_num_to in including_area_num_set:
            G[area_num_from].add(area_num_to)

if __name__ == '__main__':
    solve()

Fixed submission:
from collections import deque
def solve():
    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())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' or V[h][w] != -1:
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    s = V[Ch][Cw]
    g = V[Dh][Dw]

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)
    
    print(dist[g])

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict, deque
def solve():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch -= 1
    Cw -= 1
    Dh,Dw = map(int,input().split())
    Dh -= 1
    Dw -= 1

    S = [list(input()) for _ in range(H)]
    area_num = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                dfs(h,w,H,W,S,area_num)
                area_num += 1

    start_area_num = int(S[Ch][Cw])
    goal_area_num = int(S[Dh][Dw])

    area_num_count = area_num + 1

    # G = defaultdict(set)
    G = [set() for _ in range(area_num_count)]

    for h in range(H):
        for w in range(W):
            from_area_num = S[h][w]
            if from_area_num == '#':
                continue
            from_area_num = int(from_area_num)

            d = ((0,-1),(0,1),(-1,0),(1,0))
            close_to_wall = False
            for dh, dw in d:
                if dh+h < 0 or dh+h >= H:
                    continue
                if dw+w < 0 or dw+w >= W:
                    continue

                if S[dh+h][dw+w] == '#':
                    close_to_wall = True
            
            if not close_to_wall:
                continue

            for dh in range(2+1):
                if h+dh < 0 or h+dh >= H:
                    continue
                for dw in range(-2,2+1):
                    if w+dw < 0 or w+dw >= W:
                        continue
                    to_area_num = S[h+dh][w+dw]
                    if to_area_num == '#':
                        continue
                    to_area_num = int(to_area_num)
                    if from_area_num != to_area_num:
                        # G[to_area_num].add(from_area_num)
                        # G[from_area_num].add(to_area_num)
                        G[to_area_num].add(from_area_num)
                        G[from_area_num].add(to_area_num)
    
    visited = [False] * area_num_count
    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        visited[cur_area_num] = True
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                q.append((next_area_num,warp_cnt+1))
    else:
        print(-1)

def dfs(h,w,H,W,S,area_num):
    if 0 <= h < H and 0 <= w < W and S[h][w] == '.':
        S[h][w] = str(area_num)
        dfs(h+1,w,H,W,S,area_num)
        dfs(h,w+1,H,W,S,area_num)
        dfs(h-1,w,H,W,S,area_num)
        dfs(h,w-1,H,W,S,area_num)

def mod_graph(G,including_area_num_set):
    for area_num_from in including_area_num_set:
        for area_num_to in including_area_num_set:
            G[area_num_from].add(area_num_to)

if __name__ == '__main__':
    solve()

Fixed submission:
from collections import deque
def solve():
    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())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' or V[h][w] != -1:
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    s = V[Ch][Cw]
    g = V[Dh][Dw]

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)
    
    print(dist[g])

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict, deque
def solve():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch -= 1
    Cw -= 1
    Dh,Dw = map(int,input().split())
    Dh -= 1
    Dw -= 1

    S = [list(input()) for _ in range(H)]
    area_num = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                dfs(h,w,H,W,S,area_num)
                area_num += 1

    start_area_num = int(S[Ch][Cw])
    goal_area_num = int(S[Dh][Dw])

    G = defaultdict(set)

    for h in range(H):
        for w in range(W):
            from_area_num = S[h][w]
            if from_area_num == '#':
                continue
            from_area_num = int(from_area_num)

            d = ((0,-1),(0,1),(-1,0),(1,0))
            close_to_wall = False
            for dh, dw in d:
                if dh+h < 0 or dh+h >= H:
                    continue
                if dw+w < 0 or dw+w >= W:
                    continue

                if S[dh+h][dw+w] == '#':
                    close_to_wall = True
            
            if not close_to_wall:
                continue

            for dh in range(2+1):
                if h+dh < 0 or h+dh >= H:
                    continue
                for dw in range(-2,2+1):
                    if w+dw < 0 or w+dw >= W:
                        continue
                    to_area_num = S[h+dh][w+dw]
                    if to_area_num == '#':
                        continue
                    to_area_num = int(to_area_num)
                    if from_area_num != to_area_num:
                        G[to_area_num].add(from_area_num)
                        G[from_area_num].add(to_area_num)
    
    area_num_count = area_num + 1
    visited = [False] * area_num_count
    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        visited[cur_area_num] = True
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                q.append((next_area_num,warp_cnt+1))
    else:
        print(-1)

def dfs(h,w,H,W,S,area_num):
    if 0 <= h < H and 0 <= w < W and S[h][w] == '.':
        S[h][w] = str(area_num)
        dfs(h+1,w,H,W,S,area_num)
        dfs(h,w+1,H,W,S,area_num)
        dfs(h-1,w,H,W,S,area_num)
        dfs(h,w-1,H,W,S,area_num)

def mod_graph(G,including_area_num_set):
    for area_num_from in including_area_num_set:
        for area_num_to in including_area_num_set:
            G[area_num_from].add(area_num_to)

if __name__ == '__main__':
    solve()

Fixed submission:
from collections import deque
def solve():
    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())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' or V[h][w] != -1:
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    s = V[Ch][Cw]
    g = V[Dh][Dw]

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)
    
    print(dist[g])

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict, deque
def solve():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch -= 1
    Cw -= 1
    Dh,Dw = map(int,input().split())
    Dh -= 1
    Dw -= 1

    S = [list(input()) for _ in range(H)]
    area_num = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                dfs(h,w,H,W,S,area_num)
                area_num += 1

    start_area_num = int(S[Ch][Cw])
    goal_area_num = int(S[Dh][Dw])

    G = defaultdict(set)

    for h in range(H):
        for w in range(W):
            from_area_num = S[h][w]
            if from_area_num == '#':
                continue
            from_area_num = int(from_area_num)

            d = ((0,-1),(0,1),(-1,0),(1,0))
            close_to_wall = False
            for dh, dw in d:
                if dh+h < 0 or dh+h >= H:
                    continue
                if dw+w < 0 or dw+w >= W:
                    continue

                if S[dh+h][dw+w] == '#':
                    close_to_wall = True
            
            if not close_to_wall:
                continue

            for dh in range(-2,2+1):
                if h+dh < 0 or h+dh >= H:
                    continue
                for dw in range(-2, 2+1):
                    if w+dw < 0 or w+dw >= W:
                        continue
                    to_area_num = S[h+dh][w+dw]
                    if to_area_num == '#':
                        continue
                    to_area_num = int(to_area_num)
                    if from_area_num != to_area_num:
                        G[to_area_num].add(from_area_num)
                        G[from_area_num].add(to_area_num)
    
    area_num_count = area_num + 1
    visited = [False] * area_num_count
    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        visited[cur_area_num] = True
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                q.append((next_area_num,warp_cnt+1))
    else:
        print(-1)

def dfs(h,w,H,W,S,area_num):
    if 0 <= h < H and 0 <= w < W and S[h][w] == '.':
        S[h][w] = str(area_num)
        dfs(h+1,w,H,W,S,area_num)
        dfs(h,w+1,H,W,S,area_num)
        dfs(h-1,w,H,W,S,area_num)
        dfs(h,w-1,H,W,S,area_num)

if __name__ == '__main__':
    solve()

Fixed submission:
from collections import deque
def solve():
    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())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' or V[h][w] != -1:
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    s = V[Ch][Cw]
    g = V[Dh][Dw]

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)
    
    print(dist[g])

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict, deque
def solve():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch -= 1
    Cw -= 1
    Dh,Dw = map(int,input().split())
    Dh -= 1
    Dw -= 1

    S = [list(input()) for _ in range(H)]
    area_num = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                dfs(h,w,H,W,S,area_num)
                area_num += 1

    start_area_num = int(S[Ch][Cw])
    goal_area_num = int(S[Dh][Dw])

    G = defaultdict(set)

    for h in range(H):
        for w in range(W):
            from_area_num = S[h][w]
            if from_area_num == '#':
                continue
            from_area_num = int(from_area_num)

            d = ((0,-1),(0,1),(-1,0),(1,0))
            close_to_wall = False
            for dh, dw in d:
                if dh+h < 0 or dh+h >= H:
                    continue
                if dw+w < 0 or dw+w >= W:
                    continue

                if S[dh+h][dw+w] == '#':
                    close_to_wall = True
            
            if not close_to_wall:
                continue

            for dh in range(-2,2+1):
                if h+dh < 0 or h+dh >= H:
                    continue
                for dw in range(-2, 2+1):
                    if w+dw < 0 or w+dw >= W:
                        continue
                    to_area_num = S[h+dh][w+dw]
                    if to_area_num == '#':
                        continue
                    to_area_num = int(to_area_num)
                    if from_area_num != to_area_num:
                        G[to_area_num].add(from_area_num)
                        G[from_area_num].add(to_area_num)
    
    area_num_count = area_num + 1
    visited = [False] * area_num_count
    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        visited[cur_area_num] = True
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                q.append((next_area_num,warp_cnt+1))
    else:
        print(-1)

def dfs(h,w,H,W,S,area_num):
    if 0 <= h < H and 0 <= w < W and S[h][w] == '.':
        S[h][w] = str(area_num)
        dfs(h+1,w,H,W,S,area_num)
        dfs(h,w+1,H,W,S,area_num)
        dfs(h-1,w,H,W,S,area_num)
        dfs(h,w-1,H,W,S,area_num)

if __name__ == '__main__':
    solve()

Fixed submission:
from collections import deque
def solve():
    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())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' or V[h][w] != -1:
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    s = V[Ch][Cw]
    g = V[Dh][Dw]

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)
    
    print(dist[g])

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict, deque
def solve():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch -= 1
    Cw -= 1
    Dh,Dw = map(int,input().split())
    Dh -= 1
    Dw -= 1

    S = [list(input()) for _ in range(H)]
    area_num = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                dfs(h,w,H,W,S,area_num)
                area_num += 1

    start_area_num = int(S[Ch][Cw])
    goal_area_num = int(S[Dh][Dw])

    G = defaultdict(set)

    for h in range(H):
        for w in range(W):
            from_area_num = S[h][w]
            if from_area_num == '#':
                continue
            from_area_num = int(from_area_num)

            for dh in range(-2,2+1):
                if h+dh < 0 or h+dh >= H:
                    continue
                for dw in range(-2, 2+1):
                    if w+dw < 0 or w+dw >= W:
                        continue
                    to_area_num = S[h+dh][w+dw]
                    if to_area_num == '#':
                        continue
                    to_area_num = int(to_area_num)
                    if from_area_num != to_area_num:
                        G[to_area_num].add(from_area_num)
                        G[from_area_num].add(to_area_num)
    
    area_num_count = area_num + 1
    visited = [False] * area_num_count
    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        visited[cur_area_num] = True
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                q.append((next_area_num,warp_cnt+1))
    else:
        print(-1)

def dfs(h,w,H,W,S,area_num):
    if 0 <= h < H and 0 <= w < W and S[h][w] == '.':
        S[h][w] = str(area_num)
        dfs(h+1,w,H,W,S,area_num)
        dfs(h,w+1,H,W,S,area_num)
        dfs(h-1,w,H,W,S,area_num)
        dfs(h,w-1,H,W,S,area_num)

if __name__ == '__main__':
    solve()

Fixed submission:
from collections import deque
def solve():
    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())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' or V[h][w] != -1:
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    s = V[Ch][Cw]
    g = V[Dh][Dw]

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)
    
    print(dist[g])

if __name__ == '__main__':
    solve()