1

我需要遍历布尔值的二维数组，从上边框到下边框，并确定完全由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值的路径并记录它们的坐标。

4

2 回答 2

3

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

找到true后，查看它的相邻单元格。（确切地说，哪些相邻的单元格取决于对角线是否计数以及您的路径是否可以像水槽下的疏水管一样向上弯曲。）

在此处输入图像描述

（图片来自维基百科）

如果您找到另一个包含 的单元格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

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

于 2012-11-23T17:11:06.027 回答
1

您可以将其转换为图形并运行寻路算法。

将每个矩阵条目变成图上的一个节点。对于位于矩阵的每个true节点[i,j]，将其连接到具有值的最接近的四个相邻条目中的每一个true，即，[i+/-1, j]每当[i, j+/-1]这样的条目为真时，都将其连接到条目。这些都是图上的所有且唯一的边。然后在位于顶部边界的所有节点上运行 Dijkstra 算法http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm 。只要有这样的路径，就会true返回每个节点对之间的最短路径。true

于 2012-11-23T18:40:58.627 回答