Problem p02579 (python)

Fixed submission:
from collections import deque
# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    d = [[float("inf")] * m for i in range(n)]
    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    sx = c[0]
    sy = c[1]
    gx = g[0]
    gy = g[1]

    # 周辺25マス移動
    dd = []
    for i in range(-2,3):
        for j in range(-2,3):
            dd.append([i,j])

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0
    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == "." and d[nx][ny] > d[p[0]][p[1]]:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.appendleft((nx, ny))
                d[nx][ny] = d[p[0]][p[1]]
        for i in range(25):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dd[i][0]
            ny = p[1] + dd[i][1]
            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == "." and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]]+1

    return d[gx][gy]

n, m = map(int, input().split())
c = list(map(lambda x:int(x)-1,input().split()))
g = list(map(lambda x:int(x)-1,input().split()))
maze = [list(input()) for i in range(n)]

ans = bfs()
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Buggy submission (verdict: Runtime Error):
import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * (h*w) # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

h,w = map(int,input().split())
c = list(map(int,input().split()))
d = list(map(int,input().split()))
maze = [list(input()) for i in range(h)]
# eのインデックスはi*w+j
e = [[] for _ in range(h*w)]
for i in range(h):
    for j in range(w):
        if j<w-1 and maze[i][j] == "." and maze[i][j+1] == ".":
            e[i*w+j].append((0, i*w+j+1))
            e[i*w+j+1].append((0, i*w+j)) # 有向グラフでは削除
        if i<h-1 and maze[i][j] == "." and maze[i+1][j] == ".":
            e[i*w+j].append((0, (i+1)*w+j))
            e[(i+1)*w+j].append((0, i*w+j)) # 有向グラフでは削除
        for x in range(3):
            for y in range(3):
                if i+x<h and j+y<w and maze[i+x][j+y] == ".":
                    e[i*w+j].append((1, (i+x)*w+j+y))
                    e[(i+x)*w+j+y)].append((1, i*w+j)

# print(dijkstra(1))
ans = dijkstra((c[0]-1)*w+(c[1]-1))[(d[0]-1)*w+(d[1]-1)]
if ans == float("inf"):
    print(-1)
    exit()
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * (h*w) # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

h,w = map(int,input().split())
c = list(map(int,input().split()))
d = list(map(int,input().split()))
maze = [list(input()) for i in range(h)]
# eのインデックスはi*w+j
e = [[] for _ in range(h*w)]
for i in range(h):
    for j in range(w):
        if j<w-1 and maze[i][j] == "." and maze[i][j+1] == ".":
            e[i*w+j].append((0, i*w+j+1))
            e[i*w+j+1].append((0, i*w+j)) # 有向グラフでは削除
        if i<h-1 and maze[i][j] == "." and maze[i+1][j] == ".":
            e[i*w+j].append((0, (i+1)*w+j))
            e[(i+1)*w+j].append((0, i*w+j)) # 有向グラフでは削除
        for x in range(-2,3):
            for y in range(-2,3):
                if i+x<h and j+y<w and maze[i+x][j+y] == ".":
                    e[i*w+j].append((1, (i+x)*w+j+y))

# print(dijkstra(1))
ans = dijkstra((c[0]-1)*w+(c[1]-1))[(d[0]-1)*w+(d[1]-1)]
if ans == float("inf"):
    print(-1)
    exit()
print(ans)