如何检查集合的元素(坐标)是否形成连续形状

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

经典算法基于树遍历：从任意非开始遍历所有直接链接的节点。如果所有节点都可见，则图形已连接。

我在这里使用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