BFSでグリッドの２点間の最短距離を求めるPythonプログラム

N*Mのグリッドが与えられた際に、障害物を除いた道のみを通り、スタート地点からゴール地点までの最短経路を見つけるPythonプログラムを作成します。

条件

• グリッドは二次元配列の行列で与えられる。
• グリッドのサイズはN*Mで変化する。
• 上下左右のみ移動可能、斜め移動はできない。
• 障害物は # で表現され、そのセルを通過することはできない。
• 道は . で表現され、そのセルは通過することができる。
• スタート地点は S で表現され、必ず１つである。
• ゴール地点は G で表現され、必ず１つである。
• ゴール地点を発見した場合、スタート地点からゴール地点までの最短距離を出力する。
• ゴール地点を発見できなかった場合、 -1 を出力する。

アルゴリズム

重み付けがされていない為、BFS(幅優先探索)を使用して、最短経路を探します。

以下は、Wikipediaの幅優先探索ページから引用します。

幅優先探索（はばゆうせんたんさく、英: breadth first search）はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられるアルゴリズム。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「横型探索」とも言われる。
幅優先探索は解を探すために、グラフの全てのノードを網羅的に展開・検査する。最良優先探索とは異なり、ノード探索にヒューリスティクスを使わずに、グラフ全体を目的のノードがみつかるまで、目的のノードに接近しているかどうかなどは考慮せず探索する。

幅優先探索 - Wikipedia

ウィキメディア財団Contributors to Wikimedia projects

プログラム

Python3で記述します。