課題９２：迷路の最短経路
大きさが X * Y （XYともに整数）の迷路が与えられます。迷路はスタート「S」とゴール「G」、通路「_」と壁「#」からできており、１ターンあたり、隣接する上下左右４マスの通路のいずれかに移動できます。スタートからゴールまで移動可能な場合は、必要な最小のターン数を返し、不可能な場合は False を返す関数を作ってください。
ただし、
- X, Y ≤ 100
とする。
- 例1
string_maze = \
'__##_S______\n' \
'##_##____##_\n' \
'______#_____\n' \
'#_#_#______#\n' \
'__#______#_#\n' \
'#______#___#\n' \
'_#_##______#\n' \
'___###__#__G\n' \
'_###_____##_\n' \
'_#__#_______\n'
13
- 例2
string_maze = \
'__S#__#___##\n' \
'_____#___###\n' \
'__##__#__###\n' \
'_#__##___#_#\n' \
'_###_##____#\n' \
'_____#_###__\n' \
'________#_#_\n' \
'#______#_#_#\n' \
'#___#___#___\n' \
'________#G__\n'
False
- 例3
string_maze = \
'S_#_##__###_\n' \
'#___#__#__##\n' \
'_##_______#_\n' \
'___##__#_##_\n' \
'___#__#_#___\n' \
'#____#____#_\n' \
'__#_##G####_\n' \
'_____##___#_\n' \
'____##__#___\n' \
'#_#____##_#_\n' \
38
課題提出方法
-
基本的にGoogle Colaboratoryを用いてプログラミングしてください。どうしても Google Colaboratory を用いることができない場合のみ、Jupyter Notebook または Jupyter Lab を用いてください。
-
課題１つごとに、ノートブックを新規作成してください。１つのノートブックで複数の課題を解かないでください。
-
ノートブックを新規作成すると「Untitled.ipynb」のような名前になりますが、それを「学籍番号・氏名・課題番号」のような名前に変更してください。
-
質問・感想・要望などございましたらぜひ書き込んでください。
-
もし課題を解くにあたって参考になったウェブサイトがあれば、それについても触れてください。
-
課題を計算し終わった ipynb ファイルを提出するときは、指定したメールアドレスに Google Drive で共有する形で授業担当者に提出してください。