graph - 迷路をグラフに変換するには?

Question

迷路のデータ構造をグラフに変換しようとしています。迷路は、グリッドとセル間のいくつかの壁のようなものです。

maze[8][8][4] is how the maze is represented.
If maze[i][j][0] = 1 it means you can't go up from (i,j)
if maze[i][j][1] = 1 it means you can't go down from (i,j)
// and so on

この迷路をグラフに変換したいのですが、どうすればよいですか?

Answer 1

次の 2 つの方法で実行できます。

1.初期行列から隣接行列を作成します。隣接行列の形式は次のとおりです。

h[i][j] = 0, if there is no direct link from i to j 
(i and j are not neighbors in the maze)
h[i][j] = 1, if there is a direct link from i to j 
(i and j are neighbors in the maze)

2.各ノードのネイバー リストを作成します。 と の間に直接リンクがある場合j、 は のネイバー リストに含まれます。iij

Answer 2

入力データを隣接行列と考えてください。迷路は、各接続セグメントが頂点を作成するパスと考えてください。そして、各コーナーはノード (開始と終了を含む) 接続が存在する場合、マトリックスに値があります。そうでない場合は、INF または -1 を使用して、ルートがないことを伝えることができます。とにかく、ダイクストラの最短数学アルゴリズムを使用してこれを解決できます。それについては、ネット上にたくさんの情報があります。

http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/

Answer 3

すべての隣接セルについて、それらの間に壁がない場合は、グラフでそれらを接続します。