Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heappush
INF = 1e7

H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]

D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, sx, sy)]
heapify(PQ)
while PQ: # PQに候補がある限り
    _, ux, uy = heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heappush(PQ, (D[xx][yy], xx, yy))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Fixed submission:
import heapq
INF = 1e7
H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]
D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, (sx, sy))]
heapq.heapify(PQ)
while PQ: # PQに候補がある限り
    _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Buggy python submission (verdict: Runtime Error):
from heapq import heapify, heappop, heappush
INF = 1e7

H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())

S = [input() for _ in range(H)]

D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, sx, sy)]
heapify(PQ)
while PQ: # PQに候補がある限り
    _, ux, uy = heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heappush(PQ, (D[xx][yy], xx, yy))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Fixed submission:
import heapq
INF = 1e7
H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]
D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, (sx, sy))]
heapq.heapify(PQ)
while PQ: # PQに候補がある限り
    _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heappush
INF = 1e7

H,W=map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

S = [input() for _ in range(H)]

D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
def dijkstra(sx, sy):
    # Color = [[0]*(W) for _ in range(H)] # 0: 未訪問 1: Seen 2: Visited
    # P = [None]*N #親

    D[sx][sy] = 0
    # P[s] = None
    # PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。
    PQ = [(0, sx, sy)]
    heapify(PQ)
    while PQ: # PQに候補がある限り
        min_cost, ux, uy = heappop(PQ) # 最小コストなノードu
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                xx, yy = ux+dx, uy+dy
                if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                    is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                    # neighborでなければコストが1増える
                    if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                        D[xx][yy] = D[ux][uy] + is_not_neighbor
                        heappush(PQ, (D[xx][yy], xx, yy))
    

dijkstra(ch-1, cw-1)
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Fixed submission:
import heapq
INF = 1e7
H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]
D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, (sx, sy))]
heapq.heapify(PQ)
while PQ: # PQに候補がある限り
    _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heappush
INF = 1e10

H,W=map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

S = [input() for _ in range(H)]

D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
def dijkstra(sx, sy):
    # Color = [[0]*(W) for _ in range(H)] # 0: 未訪問 1: Seen 2: Visited
    # P = [None]*N #親

    D[sx][sy] = 0
    # P[s] = None
    # PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。
    PQ = [(0, sx, sy)]
    heapify(PQ)
    while PQ: # PQに候補がある限り
        min_cost, ux, uy = heappop(PQ) # 最小コストなノードu
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                xx, yy = ux+dx, uy+dy
                if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                    is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                    # neighborでなければコストが1増える
                    if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                        D[xx][yy] = D[ux][uy] + is_not_neighbor
                        heappush(PQ, (D[xx][yy], xx, yy))
    

dijkstra(ch-1, cw-1)
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Fixed submission:
import heapq
INF = 1e7
H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]
D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, (sx, sy))]
heapq.heapify(PQ)
while PQ: # PQに候補がある限り
    _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heappush
INF = 1e10
def main():
    H,W=map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())

    S = [input() for _ in range(H)]

    def dijkstra(sx, sy):
        # Color = [[0]*(W) for _ in range(H)] # 0: 未訪問 1: Seen 2: Visited
        D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
        # P = [None]*N #親

        D[sx][sy] = 0
        # P[s] = None
        # PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。
        PQ = [(0, sx, sy)]
        heapify(PQ)
        while PQ: # PQに候補がある限り
            min_cost, ux, uy = heappop(PQ) # 最小コストなノードu
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    xx, yy = ux+dx, uy+dy
                    if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                        is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                        # neighborでなければコストが1増える
                        if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                            D[xx][yy] = D[ux][uy] + is_not_neighbor
                            heappush(PQ, (D[xx][yy], xx, yy))
        return D

    D = dijkstra(ch-1, cw-1)
    if D[dh-1][dw-1] >= INF:
        print(-1)
    else:
        print(D[dh-1][dw-1])

main()

Fixed submission:
import heapq
INF = 1e7
H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]
D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, (sx, sy))]
heapq.heapify(PQ)
while PQ: # PQに候補がある限り
    _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heappush, heappushpop
from collections import deque
import sys
input = sys.stdin.readline

INF = 1e10

# class PriorityQueue:
#     """
#     優先度付きキューの
#     """
#     def __init__(self, heap):
#         self.heap = heap
#         heapify(self.heap)
    
#     def push(self, item):
#         heappush(self.heap, item)
    
#     def pop(self):
#         return heappop(self.heap)
    
#     def pushpop(self, item):
#         return heappushpop(self.heap, item)
    
#     def __call__(self):
#         return self.heap
    
#     def __len__(self):
#         return len(self.heap)
    
    

def main():
    H,W=map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())

    S = [input() for _ in range(H)]

    def dijkstra(sx, sy):
        # Color = [[0]*(W) for _ in range(H)] # 0: 未訪問 1: Seen 2: Visited
        D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
        # P = [None]*N #親

        D[sx][sy] = 0
        # P[s] = None
        # PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。
        PQ = [(0, sx, sy)]
        heapify(PQ)
        while PQ: # PQに候補がある限り

            min_cost, ux, uy = heappop(PQ) # 最小コストなノードu
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    xx, yy = ux+dx, uy+dy
                    if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                        is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                        # neighborでなければコストが1増える
                        if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                            D[xx][yy] = D[ux][uy] + is_not_neighbor
                            heappush(PQ, (D[xx][yy], xx, yy))
        return D

    D = dijkstra(ch-1, cw-1)
    if D[dh-1][dw-1] == INF:
        print(-1)
    else:
        print(D[dh-1][dw-1])

main()

Fixed submission:
import heapq
INF = 1e7
H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]
D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, (sx, sy))]
heapq.heapify(PQ)
while PQ: # PQに候補がある限り
    _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heappush, heappushpop
from collections import deque
import sys
input = sys.stdin.readline

INF = 1e10

# class PriorityQueue:
#     """
#     優先度付きキューの
#     """
#     def __init__(self, heap):
#         self.heap = heap
#         heapify(self.heap)
    
#     def push(self, item):
#         heappush(self.heap, item)
    
#     def pop(self):
#         return heappop(self.heap)
    
#     def pushpop(self, item):
#         return heappushpop(self.heap, item)
    
#     def __call__(self):
#         return self.heap
    
#     def __len__(self):
#         return len(self.heap)
    
    

def main():
    H,W=map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())

    S = [input() for _ in range(H)]

    def dijkstra(sx, sy):
        # Color = [[0]*(W) for _ in range(H)] # 0: 未訪問 1: Seen 2: Visited
        D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
        # P = [None]*N #親

        D[sx][sy] = 0
        # P[s] = None
        # PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。
        PQ = [(0, sx, sy)]
        heapify(PQ)
        while PQ: # PQに候補がある限り

            min_cost, ux, uy = heappop(PQ) # 最小コストなノードu
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    xx, yy = ux+dx, uy+dy
                    if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                        is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                        # neighborでなければコストが1増える
                        if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                            D[xx][yy] = D[ux][uy] + is_not_neighbor
                            heappush(PQ, (D[xx][yy], xx, yy))
        return D

    D = dijkstra(ch-1, cw-1)
    if D[dh-1][dw-1] == INF:
        print(-1)
    else:
        print(D[dh-1][dw-1])

main()

Fixed submission:
import heapq
INF = 1e7
H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]
D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, (sx, sy))]
heapq.heapify(PQ)
while PQ: # PQに候補がある限り
    _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heappush, heappushpop
from collections import deque
import sys
input = sys.stdin.readline

INF = 1e7

# class PriorityQueue:
#     """
#     優先度付きキューの
#     """
#     def __init__(self, heap):
#         self.heap = heap
#         heapify(self.heap)
    
#     def push(self, item):
#         heappush(self.heap, item)
    
#     def pop(self):
#         return heappop(self.heap)
    
#     def pushpop(self, item):
#         return heappushpop(self.heap, item)
    
#     def __call__(self):
#         return self.heap
    
#     def __len__(self):
#         return len(self.heap)
    
    

def main():
    H,W=map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())

    S = [["#"]*(W+2) for _ in range(H+2)]
    for i in range(1,1+H):
        tmp=list(input())
        for j in range(1,1+W):
            S[i][j]=tmp[j-1]

    idxs = []

    for row in range(1, H+1):
        for col in range(1, W+1):
            if S[row][col] == ".":
                idxs.append((row, col))

    dxdy = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    graph = {idx: deque() for idx in idxs}
    for x in range(1, H+1):
        for y in range(1, W+1):
            if S[x][y] == "#":
                continue
            idxs.append((x, y))
            for dx, dy in dxdy:
                if S[x+dx][y+dy] == ".":
                    graph[(x, y)].append((x+dx, y+dy, 0))
                    

    for idx in idxs:
        x = idx[0]
        y = idx[1]
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if x+dx<1 or x+dx>H or y+dy<1 or y+dy>W:
                    continue
                if S[x+dx][y+dy] == ".":
                    graph[idx].append((x+dx, y+dy, 1))

    def dijkstra(adj, sx, sy):
        Color = [[0]*(W+2) for _ in range(H+2)] # 0: 未訪問 1: Seen 2: Visited
        D = [[INF]*(W+2) for _ in range(H+2)] #始点からの距離(重み)
        # P = [None]*N #親

        D[sx][sy] = 0
        # P[s] = None
        # PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。
        PQ = [(0, sx, sy)]
        heapify(PQ)
        while PQ: # PQに候補がある限り

            min_cost, ux, uy = heappop(PQ) # 最小コストなノードu

            Color[ux][uy] = 1 # uをVisitedに。

            if D[ux][uy] < min_cost:
                # 更新の必要なし.
                continue

            for adj_x, adj_y, adj_w in adj[(ux, uy)]:
                if not Color[adj_x][adj_y]: #訪問済みでないなら
                    if D[ux][uy] + adj_w < D[adj_x][adj_y]: #最小コストを更新できるなら、
                        D[adj_x][adj_y] = D[ux][uy] + adj_w
                        # P[adj_idx] = u
                        # PQに(隣接要素のコスト, 隣接要素の番号)を容れる
                        heappush(PQ, (D[adj_x][adj_y], adj_x, adj_y))
                        # PQ.push((D[adj_x][adj_y], adj_x, adj_y))
        return D
    D = dijkstra(graph, ch, cw)
    if D[dh][dw] == INF:
        print(-1)
    else:
        print(D[dh][dw])

main()

Fixed submission:
import heapq
INF = 1e7
H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]
D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, (sx, sy))]
heapq.heapify(PQ)
while PQ: # PQに候補がある限り
    _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heappush, heappushpop
from collections import deque
import sys
input = sys.stdin.readline

INF = 1e7

# class PriorityQueue:
#     """
#     優先度付きキューの
#     """
#     def __init__(self, heap):
#         self.heap = heap
#         heapify(self.heap)
    
#     def push(self, item):
#         heappush(self.heap, item)
    
#     def pop(self):
#         return heappop(self.heap)
    
#     def pushpop(self, item):
#         return heappushpop(self.heap, item)
    
#     def __call__(self):
#         return self.heap
    
#     def __len__(self):
#         return len(self.heap)
    
    

def main():
    H,W=map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())

    S = [["#"]*(W+2) for _ in range(H+2)]
    for i in range(1,1+H):
        tmp=list(input())
        for j in range(1,1+W):
            S[i][j]=tmp[j-1]

    idxs = []

    for row in range(1, H+1):
        for col in range(1, W+1):
            if S[row][col] == ".":
                idxs.append((row, col))

    dxdy = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    graph = {idx: deque() for idx in idxs}
    for x in range(1, H+1):
        for y in range(1, W+1):
            if S[x][y] == "#":
                continue
            idxs.append((x, y))
            for dx, dy in dxdy:
                if S[x+dx][y+dy] == ".":
                    graph[(x, y)].append((x+dx, y+dy, 0))
                    

    for idx in idxs:
        x = idx[0]
        y = idx[1]
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if x+dx<1 or x+dx>H or y+dy<1 or y+dy>W:
                    continue
                if S[x+dx][y+dy] == ".":
                    graph[idx].append((x+dx, y+dy, 1))

    def dijkstra(adj, sx, sy):
        Color = [[0]*(W+2) for _ in range(H+2)] # 0: 未訪問 1: Seen 2: Visited
        D = [[INF]*(W+2) for _ in range(H+2)] #始点からの距離(重み)
        # P = [None]*N #親

        D[sx][sy] = 0
        # P[s] = None
        # PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。
        PQ = [(0, sx, sy)]
        heapify(PQ)
        while PQ: # PQに候補がある限り

            min_cost, ux, uy = heappop(PQ) # 最小コストなノードu

            Color[ux][uy] = 1 # uをVisitedに。

            if D[ux][uy] < min_cost:
                # 更新の必要なし.
                continue

            for adj_x, adj_y, adj_w in adj[(ux, uy)]:
                if not Color[adj_x][adj_y]: #訪問済みでないなら
                    if D[ux][uy] + adj_w < D[adj_x][adj_y]: #最小コストを更新できるなら、
                        D[adj_x][adj_y] = D[ux][uy] + adj_w
                        # P[adj_idx] = u
                        # PQに(隣接要素のコスト, 隣接要素の番号)を容れる
                        heappush(PQ, (D[adj_x][adj_y], adj_x, adj_y))
                        # PQ.push((D[adj_x][adj_y], adj_x, adj_y))
        return D
    D = dijkstra(graph, ch, cw)
    if D[dh][dw] == INF:
        print(-1)
    else:
        print(D[dh][dw])

main()

Fixed submission:
import heapq
INF = 1e7
H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]
D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, (sx, sy))]
heapq.heapify(PQ)
while PQ: # PQに候補がある限り
    _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heappush, heappushpop
from collections import deque


INF = 1e7

class PriorityQueue:
    """
    優先度付きキューの
    """
    def __init__(self, heap):
        self.heap = heap
        heapify(self.heap)
    
    def push(self, item):
        heappush(self.heap, item)
    
    def pop(self):
        return heappop(self.heap)
    
    def pushpop(self, item):
        return heappushpop(self.heap, item)
    
    def __call__(self):
        return self.heap
    
    def __len__(self):
        return len(self.heap)
    
    



def main():
    H,W=map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())

    S = [["#"]*(W+2) for _ in range(H+2)]
    for i in range(1,1+H):
        tmp=list(input())
        for j in range(1,1+W):
            S[i][j]=tmp[j-1]

    idxs = []

    for row in range(1, H+1):
        for col in range(1, W+1):
            if S[row][col] == ".":
                idxs.append((row, col))

    dxdy = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    graph = {idx: deque() for idx in idxs}
    for x in range(1, H+1):
        for y in range(1, W+1):
            if S[x][y] == "#":
                continue
            idxs.append((x, y))
            for dx, dy in dxdy:
                if S[x+dx][y+dy] == ".":
                    graph[(x, y)].append((x+dx, y+dy, 0))
                    

    for idx in idxs:
        x = idx[0]
        y = idx[1]
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if x+dx<1 or x+dx>H or y+dy<1 or y+dy>W:
                    continue
                if S[x+dx][y+dy] == ".":
                    graph[idx].append((x+dx, y+dy, 1))

    def dijkstra(adj, sx, sy):
        Color = [[0]*(W+2) for _ in range(H+2)] # 0: 未訪問 1: Seen 2: Visited
        D = [[INF]*(W+2) for _ in range(H+2)] #始点からの距離(重み)
        # P = [None]*N #親

        D[sx][sy] = 0
        # P[s] = None
        PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。

        while PQ: # PQに候補がある限り

            min_cost, ux, uy = PQ.pop() # 最小コストなノードu

            Color[ux][uy] = 1 # uをVisitedに。

            if D[ux][uy] < min_cost:
                # 更新の必要なし.
                continue

            for adj_x, adj_y, adj_w in adj[(ux, uy)]:
                if not Color[adj_x][adj_y]: #訪問済みでないなら
                    if D[ux][uy] + adj_w < D[adj_x][adj_y]: #最小コストを更新できるなら、
                        D[adj_x][adj_y] = D[ux][uy] + adj_w
                        # P[adj_idx] = u
                        # PQに(隣接要素のコスト, 隣接要素の番号)を容れる
                        PQ.push((D[adj_x][adj_y], adj_x, adj_y))
                        
        
        return D
    D = dijkstra(graph, ch, cw)
    if D[dh][dw] == INF:
        print(-1)
    else:
        print(D[dh][dw])

main()

Fixed submission:
import heapq
INF = 1e7
H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]
D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, (sx, sy))]
heapq.heapify(PQ)
while PQ: # PQに候補がある限り
    _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heappush, heappushpop
from collections import deque
import sys
input = sys.stdin.readline

INF = 1e10

class PriorityQueue:
    """
    優先度付きキューの
    """
    def __init__(self, heap):
        self.heap = heap
        heapify(self.heap)
    
    def push(self, item):
        heappush(self.heap, item)
    
    def pop(self):
        return heappop(self.heap)
    
    def pushpop(self, item):
        return heappushpop(self.heap, item)
    
    def __call__(self):
        return self.heap
    
    def __len__(self):
        return len(self.heap)
    
    

def dijkstra(adj, sx, sy):
    Color = [[0]*(W+2) for _ in range(H+2)] # 0: 未訪問 1: Seen 2: Visited
    D = [[INF]*(W+2) for _ in range(H+2)] #始点からの距離(重み)
    # P = [None]*N #親

    D[sx][sy] = 0
    # P[s] = None
    PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。

    while PQ: # PQに候補がある限り

        min_cost, ux, uy = PQ.pop() # 最小コストなノードu

        Color[ux][uy] = 1 # uをVisitedに。

        if D[ux][uy] < min_cost:
            # 更新の必要なし.
            continue

        for adj_x, adj_y, adj_w in adj[(ux, uy)]:
            if not Color[adj_x][adj_y]: #訪問済みでないなら
                if D[ux][uy] + adj_w < D[adj_x][adj_y]: #最小コストを更新できるなら、
                    D[adj_x][adj_y] = D[ux][uy] + adj_w
                    # P[adj_idx] = u
                    # PQに(隣接要素のコスト, 隣接要素の番号)を容れる
                    PQ.push((D[adj_x][adj_y], adj_x, adj_y))
                    
    
    return D


H,W=map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

S = [["#"]*(W+2) for _ in range(H+2)]
for i in range(1,1+H):
    tmp=list(input())
    for j in range(1,1+W):
        S[i][j]=tmp[j-1]

idxs = []

for row in range(1, H+1):
    for col in range(1, W+1):
        if S[row][col] == ".":
            idxs.append((row, col))

dxdy = [(0, 1), (0, -1), (1, 0), (-1, 0)]
graph = {idx: deque() for idx in idxs}
for x in range(1, H+1):
    for y in range(1, W+1):
        if S[x][y] == "#":
            continue
        idxs.append((x, y))
        for dx, dy in dxdy:
            if S[x+dx][y+dy] == ".":
                graph[(x, y)].append((x+dx, y+dy, 0))
                

for idx in idxs:
    x = idx[0]
    y = idx[1]
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if x+dx < 1 or x+dx>H or y+dy<1 or y+dy>W:
                continue
            if S[x+dx][y+dy] == ".":
                graph[idx].append((x+dx, y+dy, 1))

D = dijkstra(graph, ch, cw)
if D[dh][dw] == INF:
    print(-1)
else:
    print(D[dh][dw])

Fixed submission:
import heapq
INF = 1e7
H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]
D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, (sx, sy))]
heapq.heapify(PQ)
while PQ: # PQに候補がある限り
    _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heappush, heappushpop

INF = 1e10


class PriorityQueue:
    """
    優先度付きキューの
    """
    def __init__(self, heap):
        self.heap = heap
        heapify(self.heap)
    
    def push(self, item):
        heappush(self.heap, item)
    
    def pop(self):
        return heappop(self.heap)
    
    def pushpop(self, item):
        return heappushpop(self.heap, item)
    
    def __call__(self):
        return self.heap
    
    def __len__(self):
        return len(self.heap)
    

def dijkstra(adj, sx, sy):
    Color = [[0]*(W+2) for _ in range(H+2)] # 0: 未訪問 1: Seen 2: Visited
    D = [[INF]*(W+2) for _ in range(H+2)] #始点からの距離(重み)
    # P = [None]*N #親

    D[sx][sy] = 0
    # P[s] = None
    PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。

    while PQ: # PQに候補がある限り

        min_cost, ux, uy = PQ.pop() # 最小コストなノードu

        Color[ux][uy] = 2 # uをVisitedに。

        if D[ux][uy] < min_cost:
            # 更新の必要なし.
            continue

        for adj_element in adj[(ux, uy)]:
            adj_x, adj_y, adj_w = adj_element
            if Color[adj_x][adj_y] != 2: #訪問済みでないなら
                if D[ux][uy] + adj_w < D[adj_x][adj_y]: #最小コストを更新できるなら、
                    D[adj_x][adj_y] = D[ux][uy] + adj_w
                    # P[adj_idx] = u
                    # PQに(隣接要素のコスト, 隣接要素の番号)を容れる
                    PQ.push((D[adj_x][adj_y], adj_x, adj_y))
                    Color[adj_x][adj_y] = 1
    
    return D


from collections import deque
import sys
input = sys.stdin.readline

H,W=map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

S = [["#"]*(W+2) for _ in range(H+2)]
for i in range(1,1+H):
    tmp=list(input())
    for j in range(1,1+W):
        S[i][j]=tmp[j-1]

idxs = []
for row in range(1, H+1):
    for col in range(1, W+1):
        if S[row][col] == ".":
            idxs.append((row, col))

dxdy = [(1,0), (-1,0), (0,1), (0,-1)]
graph = {idx: deque() for idx in idxs}
for idx in idxs:
    x = idx[0]
    y = idx[1]
    for dx, dy in dxdy:
        if S[x+dx][y+dy] == ".":
            graph[idx].append((x+dx, y+dy, 0))

for idx in idxs:
    x = idx[0]
    y = idx[1]
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if x+dx < 1 or x+dx>H or y+dy<1 or y+dy>W:
                continue
            if S[x+dx][y+dy] == ".":
                graph[idx].append((x+dx, y+dy, 1))

D = dijkstra(graph, ch, cw)
if D[dh][dw] == INF:
    print(-1)
else:
    print(D[dh][dw])

Fixed submission:
import heapq
INF = 1e7
H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]
D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, (sx, sy))]
heapq.heapify(PQ)
while PQ: # PQに候補がある限り
    _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])