3


0

多次元配列でのパス検索

経路探索の概念と、プログラムがポイントAからポイントBを探す方法を最も効率的な方法で理解し、A *の概念に漠然と理解しています。 しかし、もしも迷路を通る道を見つけようとするのではなく、閉ざされた迷路の中で最も長い廊下を見つけようとしている場合、その廊下は対角線上にはありません。

これが私の迷路の例です:

1 1 0 1
0 0 1 1
1 0 1 0
1 0 1 0

許可されたパスとして1を使用し、無効なパスとして0を使用する場合、最長パスは5で、座標は(0,3)、(1,2)、(1,3)、(2,2)、(3、 2)。

この情報を再帰的に見つけるにはどうすればよいですか?

私は(0,0)から開始し、上下左右に移動してそれらが可能な動きかどうかを確認する方法について頭を悩ませてきましたが、私が思いつくバージョンでは重複と繰り返しカウントに遭遇します。

3 回答


1


私はhttp://en.wikipedia.org/wiki/Flood_fill[flood fill]アルゴリズムを見ます。

基本的に最初の `1`から開始します-そこから塗りつぶし、塗りつぶされた位置をカウントします。 これらを0に設定し(移動しても)、繰り返します。

この問題を並列化する方法もあると思います。


0


配列をグラフとして表すことができます(1が頂点であり、対応する1が隣接している場合に2つの頂点が接続されている場合)。 +次に、グラフの直径を見つけます。 (直径は最長のパスです)。 +直径を見つける方法については、http://www.cs.auckland.ac.nz/~ute/220ft/graphalg/node19.html [こちら]をご覧ください。


0


DFSはまさにあなたが望むものです。 コードは次のようになります。

int[,] map = InitTheMapHere();
int longest = -1;
int currentLength = 0;
void TryStep(int x,int y)
{
   if (map[x][y]==0 or over the edge)  //update the longest and return

      TryStep(go up);
      TryStep(go down);
      TryStep(go left);
      TryStep(go right);
}