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

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

将形成这个形状，因此它不会是连续的，但我的代码认为它是连续的

xxxo
xoxo
xoxo
xxxx

这在大多数情况下都有效，但当给定的字符形成两个独立的连续形状时（如我上面给出的第二个错误示例）就不起作用了。我试图通过在检查每个元组之后删除它来解决这个问题，但是我得到了

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