如何检查集合的元素（坐标）是否形成连续形状？

Question

我正在尝试编写一个函数，该函数获取一组元组作为参数，并检查给定的字符是否在NxN网格中形成连续形状。元组是构成网格的列表中的字符的索引。如果另一个字符的正下方、上方或侧面有一个字符，则该形状是连续的。continuous             not continous         not continous  xxxxx                   xxxxx                 ooxxx     xxoox                   xxoox                 xxxxx  xxxoo                   ooxxx                 xxoox   xxxoo                   oxxxx                 xxoox  xxxxo                   xoxxx                 xxxxx ========================    def connected(characters):        result = True        for i in characters:            if (i[0]+1, i[1]) in characters or (i[0]-1, i[1]) in characters or (i[0], i[1]+1) in characters or (i[0], i[1]-1) in characters:                result = True                characters.discard(i)            else:                result = False                return result        return result>>>connected({(1, 3), (2, 1), (2, 3), (0, 3), (1, 1)})将形成这种形状，因此它不会是连续的，但我的代码认为它是连续的。xxxoxoxoxoxoxxxx这在大多数情况下都有效，但是当给定的字符形成两个单独的连续形状时不起作用，就像我上面给出的第二个错误示例一样。我试图通过在检查后删除每个元组来解决此问题，但我得到Traceback (most recent call last):  File "C:/Users/User/PycharmProjects/untitled6/venv/1.py", line 47, in <module>    connected({(1, 2), (1, 3), (2, 2), (0, 3), (0, 4)})  File "C:/Users/User/PycharmProjects/untitled6/venv/1.py", line 15, in connected    for i in grid:RuntimeError: Set changed size during iteration错误。我能做些什么来解决这个问题？

Answer 1

有关错误的详细信息，请参阅 https://stackoverflow.com/a/38423075。基本上，如果要在循环中修改该集合，则必须循环访问该集合的副本。

除此之外，您的算法中还存在一个缺陷。

如果不丢弃当前字符，则仅当每个字符都有邻居时才进行检查。这是可以的：

xxxxx

xoxox

xoxox

xxxxx

但是，如果您丢弃当前字符，则可能会有以下情况：

 xxx            xxx

 xox <- cur     x x <- discarded

 xox            xox <- has no neighbor!

 xxx            xxx

经典算法基于树遍历：从任何 not 开始，遍历所有直接链接的节点。如果看到所有节点，则图形已连接。

我在这里使用DFS，但如果你愿意，你可以使用BFS：

def connected(characters):

    seen = set()

    stack = [next(iter(characters))] if characters else []

    while stack:

        c = stack.pop()

        seen.add(c)

        for other_c in [(c[0]+1, c[1]), (c[0]-1, c[1]), (c[0], c[1]+1), (c[0], c[1]-1)]:

            if other_c not in seen and other_c in characters:

                stack.append(other_c)

    return not (characters - seen)

print(connected({(1, 3), (2, 1), (2, 3), (0, 3), (1, 1)}))

# False

print(connected({(1, 3), (2, 1), (2, 3), (0, 3), (1, 1), (1, 2)}))

# True