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

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。基本上，如果要在循环中修改该集合，则必须循环访问该集合的副本。除此之外，您的算法中还存在一个缺陷。如果不丢弃当前字符，则仅当每个字符都有邻居时才进行检查。这是可以的：xxxxxxoxoxxoxoxxxxxx但是，如果您丢弃当前字符，则可能会有以下情况：&nbsp;xxx&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; xxx&nbsp;xox <- cur&nbsp; &nbsp; &nbsp;x x <- discarded&nbsp;xox&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; xox <- has no neighbor!&nbsp;xxx&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; xxx经典算法基于树遍历：从任何 not 开始，遍历所有直接链接的节点。如果看到所有节点，则图形已连接。我在这里使用DFS，但如果你愿意，你可以使用BFS：def connected(characters):&nbsp; &nbsp; seen = set()&nbsp; &nbsp; stack = [next(iter(characters))] if characters else []&nbsp; &nbsp; while stack:&nbsp; &nbsp; &nbsp; &nbsp; c = stack.pop()&nbsp; &nbsp; &nbsp; &nbsp; seen.add(c)&nbsp; &nbsp; &nbsp; &nbsp; for other_c in [(c[0]+1, c[1]), (c[0]-1, c[1]), (c[0], c[1]+1), (c[0], c[1]-1)]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if other_c not in seen and other_c in characters:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; stack.append(other_c)&nbsp; &nbsp; return not (characters - seen)print(connected({(1, 3), (2, 1), (2, 3), (0, 3), (1, 1)}))# Falseprint(connected({(1, 3), (2, 1), (2, 3), (0, 3), (1, 1), (1, 2)}))# True