java - 如何找到连接假值二维数组边界的真值路径

Question

我需要遍历一个 boolean 值的二维数组，从上边界到下边界，并确定一条完全由 true 值组成的路径。在这一点上，我尝试了许多不同的技术，但我没有取得任何进展。有人可以帮我吗？

举个例子:

false true  true  false false false
false true  false false false false
false true  true  false false false
false false true  false false false

我需要找到一种方法来确定边界上的 true 值，然后找到一种方法遍历 true 值的路径。

#..###
#.####
#..###
##.###

此时我已开始使用算法。我想过遍历列并搜索 true 值，将行递增一个，然后搜索最后一行，但我不知道如何处理第一列和最后一列。

问题的第一部分是确定 true 值沿边界的位置。第二部分是找到 true 值的路径并记录它们的坐标。

Answer 1

这可以通过简单的试错算法来解决。从上到下的要求很好，因为您知道必须从数组的第一行开始，所以您所要做的就是在该行中搜索 true 值作为开始。

一旦找到 true，请查看它的相邻单元格。 (究竟哪些相邻单元格取决于对角线是否计数以及您的路径是否可以像水槽下的存水弯管道一样向上弯曲。)

(图片来自Wikipedia)

如果您找到另一个包含 true 的单元格，那么该单元格将成为您的“当前”单元格，并且您可以查看它的 邻居。继续这样做，直到到达最后一行中的 true 单元格。或者，如果您没有找到任何 true 邻居，则返回到前一个单元并继续其邻居。

这样做的一种方法是使用递归和非常少的代码。只需做类似的事情

// pseudocode only
for(Cell foo : all cells in top row)
    checkCell(foo);

boolean checkCell(Cell current) {
    if(current == false)
        return false;

    if(current == true && current.isInLastRow == true)
        return true;

    // if we reach here, the cell is true but we're not done
    for(Cell foo : all valid neighbors of this cell except the "parent")
        return checkCell(foo);
}

另一种方式使用更多内存，但也更高效。创建第二个数组，与原始数组大小相同。当您测试原始数组中的单元格时，请在新数组中标记其对应的单元格。然后，当您测试邻居时，检查新数组以查看您是否已经去过给定的邻居。如果你有，跳过它，因为它不会导致成功(你知道这一点是因为如果可以的话你已经完成并返回了)。如果数组包含许多彼此相邻的 true 值，例如

，这可以为您节省很多时间

F T T T F
F T T T F
F T T T F
F T T T F
F T T T F

编辑:
我错过了您的更新评论，该评论说您需要记录路径中单元格的坐标。没问题:只需创建一个 stack的 Point objects记录你去过的地方。如果您最终走错了路，只需在每次“返回一个级别”时从堆栈中弹出一次即可。