[Python] BFS（幅優先探索） ABC007C

#ABC1007C
問題文にとても分かり易い説明がある。
参考
BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜

サンプルコード

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]

    for i in range(n):
        for j in range(m):
            # 地図情報にスタートとゴールを設定
            if maze[i][j] == "S":
                sx = i
                sy = j
            if maze[i][j] == "G":
                gx = i
                gy = j

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # BFS本体 キューが空になるまでループ
    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] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


n, m = map(int, input().split())
# リストのリストとして読込
maze = [list(input()) for i in range(n)]

print(bfs())