3

私は、パスファインディングの概念と、プログラムが最も効率的な方法でポイント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）から始めて、上、下、左、右に移動して、それらが可能な動きであるかどうかを確認する方法について頭を悩ませてきましたが、私が思いついたバージョンでは、重複と繰り返しのカウントが発生します。

4

3 に答える 3

1

フラッド フィルアルゴリズムを見てみましょう。

基本的には最初から始めます1- そこから塗りつぶし、塗りつぶされたポジションを数えます。それらを 0 に設定し (たとえ行っても)、繰り返します。

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

于 2010-10-13T06:55:08.960 に答える
0

配列をグラフとして表すことができます (1 が頂点で、対応する 1 が隣接している場合は 2 つの頂点が接続されている場合)。
次に、グラフの直径を見つけます (直径は最長パスです)。方法については、こちら
を参照し てください。直径を見つけます。

于 2010-10-13T07:02:35.313 に答える
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);
}
于 2010-10-13T07:06:13.927 に答える