检查布尔二维列表中的两点是否相连

Question

有没有快速的方法可以找出 2D 布尔区域上的两个点是否相连，并且您只能在值为 True 的正方形上上下左右移动？假设您有以下 6x6 2D 列表：

在代码中，那就是：

bool2DList = [6][6]
bool2DList = { True,  True,  False, False, True,  True,
               False, True,  True,  False, True,  True,
               False, True,  True,  False, False, True,
               False, False, False, False, False, True,
               False, False, False, False, True,  True,
               False, True,  True,  True,  True,  True }

绿色方块的值为 True，蓝色方块的值为 False。我正在考虑函数（它可能需要递归），其中您将一个 2D 列表作为参数，与几个点的元组（坐标）列表一起放置，最后是一个特殊点的元组，它可以有标题像这样：

def FindWay( bool2DList,listOfPoints,specialPointCoord )

在此示例中，特殊点是坐标为 5;1 的点 P。让我们想象一下您将从那些特殊点开始步行。如果不踩到蓝色方块，你能到达哪些点？在此示例中，只有点 P4 和 P5 （输出可以是这些点的坐标，即 0;5 和 5;3 ）。它可能需要递归，但我不知道身体应该是什么样子。

谢谢。

Answer 1

恐怕没有什么简单的方法可以做到这一点。这是一个图遍历问题，Python 没有支持该问题的内置函数。我希望您需要一个广度优先图搜索的简单实现。

简而言之，您保留了已访问过但未处理过的节点的列表；您处理过的另一个节点列表。步骤如下所示：

已处理= []访问= [P]当访问不为空时：从访问列表中删除您可以直接从A到达的每个节点B的访问列表中的节点A：如果B是新的（不在访问或处理列表中）：将B放在已访问列表将 A 放入已处理列表中

这将找到您可以到达的所有节点。如果您担心某个特定节点，请在循环内检查B是否是您的目标节点。当你将B放入访问列表时，将其放在前面表示深度优先，放在后面表示广度优先。

在此应用程序中，“您可以到达的所有节点”由具有相同布尔标签的边界节点组成。