c# - 多维数组中的路径查找

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) 开始向上、向下、向左、向右移动，看看这些是否可能移动，但我想出的任何版本都会遇到重复和重复计数。

Answer 1

我会看一个洪水填充算法。

基本上从第一个开始1- 从那里填充填充，并计算填充位置。将它们设置为 0（即使你去），然后重复。

我认为也有一些方法可以并行化这个确切的问题。

Answer 2

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

Answer 3

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