与えられた迷路のデータ構造を選択するにはどうしたらいいですか？

Question

私は迷路の問題を以下の図に示すように持っています。

これは6x6マトリクスと見なすことができますが、目標は特定の着色ブロックの出口を見つけることです。私が見た迷路の問題に基づいて、dfsを使うのではなく、bfsを適用するのが良いアイデアかもしれないと思います。しかし、私は、2つ以上のノードを保持できるツリーをどのように実装できるのか混乱しています。木の代わりに使うことができる他のデータ構造はありますか？たぶん、グラフ？また、迷路問題を解決するためにbfsやdfsを適用することを尋ねられる多くの質問がありますが、A *検索アルゴリズムを適用するケースは見たことがありません。それは効率と実装はどうですか？私が進歩できるというヒントを私に与えることができれば、私は高く評価されるだろう。ここで

は絵です：

Answer 1

あなたは「M」ウェイ・ツリーを実装することができます用語のhttp://webdocs.cs.ualberta.ca/~holte/T26/m-way-trees.html

Answer 2

注：グラフがあるため、ツリー、木に代わるものではありませんがグラフの一種です。あなたが探している言葉は格子だと思います。

これは、X * Yノードと最大4つの接続（北、南、東、西）を持つ各ノードとのマトリックス型格子として実装します。それぞれのノードと各ノードとの間の接続を開始し、一方または両方のノードが壁で占められている2つのノード間の接続をすべて削除します。

問題を表すグラフが得られたら、Dijkstra's algorithmまたはvarious othersなどを使用して解くことができます。