2023.12.28

Maze Runner: Finding the Shortest Path Using Breadth-First Search

marugotoyoten

cs50のYoutube動画「Maze Runner: Finding the Shortest Path Using Breadth-First Search」について要点と要約をまとめました

３つの要点

要点１
Maze Runnerは、幅優先探索を使用して迷路内の最短経路を見つけるゲームです。
要点２
プログラムは、迷路を表現し、訪れたセルを追跡し、最短経路を決定するために構造体とBFS関数を実装しています。
要点３
迷路は解析され、幅優先探索が実行され、逆順のセルのリンクリストを組み立てて最短経路が印刷されます。

要約

Maze Runner: 問題と解決手法の紹介
Maze Runnerは、プレイヤーに迷路のスタートから出口までの最短経路を見つけることを挑戦するゲームです。この問題は、幅優先探索を使用して解決することができます。幅優先探索では、開始地点からある一定のステップ数離れたセルの範囲を拡大していきます。各可能な次の移動を見ながら、目的地に到達するまで徐々に探索範囲を広げることができます。幅優先探索の各ステップでは、各セルから前のセルへのパスがマークされ、最速の経路を決定することができます。

構造体とBFS関数の実装
座標や迷路との作業を容易にするために、座標を格納する構造体や、各方向の壁の存在を示すセルなどの構造体を定義します。また、幅優先探索を表現するために、ホライズンと呼ばれるキューを使用します。BFS関数はプログラムの中核であり、探索の各ステップで実行されます。セルが以前に訪れたことがあるかどうかをチェックし、訪れていない場合はキューに追加します。各セルから前のセルへの矢印が描かれ、最短経路を決定するのに役立つポインタが作成されます。

迷路の解析と幅優先探索の実行
入力はASCII文字形式で迷路が提供されます。迷路を文字列として読み込み、その寸法を決定します。セルのデータを壁の垂直および水平方向を識別するために解析し、セルデータを更新します。準備された迷路で、訪れたセルと前のセルを指す矢印を追跡するためのテーブルを初期化します。幅優先探索は、開始セルをキューに追加し、ホライズンを繰り返し拡大して終了するか、ボード全体が埋まるまで続けます。

最短経路の印刷
幅優先探索が完了すると、最短経路を表すセルと矢印が得られます。開始から終了までのパスを印刷するために、終了から始まり、矢印に従って前のセルに進むことで逆順のリンクリストを組み立てます。次に、リンクリストを順方向に繰り返し、方向を印刷します。パスは、迷路の右下隅に到達するまで続きます。このプロセスに従うことで、Maze Runnerは与えられた迷路を効率的に最短経路で解決します。

▼今回の動画