在多维数组中寻找路径

Question

我有点理解路径规划的概念，以及程序如何以最有效的方式从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) 开始向上、下、左、右移动以查看是否存在可能的移动，但是我想出的任何版本都会遇到重复和重复计数的问题。

- bafromca

Answer 1

我会看一下泛洪填充算法。

基本上从第一个1开始 - 从那里进行泛洪填充，并计算填充的位置。即使在进行时，将这些位置设置为0并重复执行。

我认为还有方法可以并行化解决这个问题。

- sje397

Answer 2

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);
}

- Cheng Chen

Answer 3

你可以将数组表示为图形（其中1是顶点，如果它们对应的1相邻，则两个顶点相连）。
然后找到图的直径（直径是最长的路径）。
请参考这里了解如何找到直径。

- Itay Karo