Pythonで理解する蟻本「2-1 迷路の最短路」(p.37) - クルトンのプログラミング教室

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-1 迷路の最短路」(p.37)
のコードをPythonで書き直したものとなっています。

入力
入力例
解答

入力

$N\,M\\(大きさ{N}\times{M}の迷路)$

入力例

10 10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#

解答

# 両端キューをインポートする
from collections import deque

INF = 100000000

# 入力
N, M = map(int,input().split())
maze = [list(input()) for _ in range(N)] # 迷路を表す文字列の配列
for x in range(N):
    for y in range(M):
        if maze[x][y] == 'S':            # スタートの座標
            sx = x
            sy = y
        if maze[x][y] == 'G':            # ゴールの座標
            gx = x
            gy = y
d = [[INF] * M for _ in range(N)]          # 各点までの最短距離の配列(INFで初期化)

# 移動4方向のベクトル
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

# (sx, sy)から(gx,gy)への最短距離を求める
# 辿り着けないとINF
def bfs():
    que = deque()
    # スタート地点を両端キューに入れ、その点の距離を0にする
    que.append([sx, sy])
    d[sx][sy] = 0

    # 両端キューが空になるまでループ
    while len(que) != 0:
        # キューの先端を取り出す
        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] == INF:
                # 移動できるならキューに入れ、その点の距離をpからの距離+1で確定する
                que.append([nx, ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d[gx][gy]

res = bfs()
print(res)