检查矩阵中的某些元素是否具有内聚性

Question

我必须编写一个非常小的Python程序来检查某些坐标组是否都连接在一起(通过一条线,而不是对角线).接下来的两张照片显示了我的意思.在左图中,所有彩色组都是有凝聚力的,右图中没有:

我已经制作了这段代码,但它似乎没有用,而且我很困惑,有关如何解决此问题的任何想法？

def cohesive(container):
   co = container.pop()
   container.add(co)
   return connected(co, container)

def connected(co, container):
   done = {co}
   todo = set(container)
   while len(neighbours(co, container, done)) > 0 and len(todo) > 0:
       done = done.union(neighbours(co, container, done))
   return len(done) == len(container)

def neighbours(co, container, done):
   output = set()
   for i in range(-1, 2):
       if i != 0:
           if (co[0] + i, co[1]) in container and (co[0] + i, co[1]) not in done:
               output.add((co[0] + i, co[1]))
           if (co[0], co[1] + i) in container and (co[0], co[1] + i) not in done:
               output.add((co[0], co[1] + i))
   return output

这是一些应该返回的参考资料True:

cohesive({(1, 2), (1, 3), (2, 2), (0, 3), (0, 4)})

这应该返回False:

cohesive({(1, 2), (1, 4), (2, 2), (0, 3), (0, 4)})

两种测试都有效,但是当我尝试使用不同的数字进行测试时,功能会失败.

Answer 1

如果可能的话，您可以只获取一个元素并附加它的邻居。

def dist(A,B):return abs(A[0]-B[0]) + abs(A[1]-B[1])

def grow(K,E):return {M for M in E for N in K if dist(M,N)<=1}

def cohesive(E):
    K={min(E)} # an element 
    L=grow(K,E)
    while len(K)<len(L) : K,L=L,grow(L,E)
    return len(L)==len(E)

grow(K,E)返回 的邻域K。

In [1]: cohesive({(1, 2), (1, 3), (2, 2), (0, 3), (0, 4)})
Out[1]: True

In [2]: cohesive({(1, 2), (1, 4), (2, 2), (0, 3), (0, 4)})
Out[2]: False