在网格中计算连接的点

我有一个m×n个网格单元格。其中一些是开关状态。找到一个有效的算法来计算连接数量。在网格中计算连接的点

顶部，左侧，右侧，底部连接的许多点仍被视为1个连接。

来源

2010-08-01 Santosh

网格大小的任何限制？对于小型电网最有效的算法将（可能）不是大型电网最有效的算法。 – 2010-08-01 16:04:16

连接是什么意思？如果两个点都打开并且相邻是一个连接？ – deinst 2010-08-01 16:04:36

没有限制，我目前有40x50的网格。如果点形成一条线，它将被计为一条。 – Santosh 2010-08-01 16:47:38

以某种顺序扫描您的网格。当您到达打开的单元格时，在其上执行flood fill。

通过关闭“填充”每个单元格。完成洪水填充后，继续扫描。

原始网格中连接组件的数量等于您执行泛洪填充的次数。

来源

2010-08-01 17:03:11

+1时间复杂度最优：O（mn） – 2010-08-01 19:26:18

您可以使用Depth-first search算法。该算法可以在时间O（E）中找到任意无向图中连通分量的数量，其中E是图中边的数量。在网格上你有O（nm）边缘，因为每个顶点至多有四个邻居。

来源

2010-08-02 14:54:41 falagar

当然，这种问题的良好数据结构（“确定连接组件的数量”）是UnionFind数据结构;它会产生接近线性（网格大小）的算法。但事实证明，针对您的具体问题，这让人想起休闲编程挑战中的迷宫练习，这里有一个更原始的，甚至更好的（线性）解决方案。

（我的道歉汤姆，因为我认为这是你所追求的，但填注是这样一个通用的技术，我想这可能会承担一些细节！）

你点颜色每个连接的区域具有不同的颜色。我们的想法是，要做到这一点，您只需要跟踪如何为网格的最后一条加工线着色。诀窍是知道（a）选择什么颜色和（b）如何计算不同的连接区域。

def countConnectedAreas(grid, n): 
    vector = [0] * n # Buffer vector containing current zones. 
    count = 0   # Current number of connected areas. 
    nextToken = 1  # Next color to use to paint a newly encountered zone. 

    for line in grid: 
    current = 0 
    for i in range(n): 
     if not line[i]: 
     # Not dot. 
     current = 0 
     else: 
     # There is a dot. 
     if current != 0 and vector[i] != 0 and current != vector[i]: 
      # This is the tricky case: it means you can paint the next 
      # square with two colors, which means that two connected 
      # areas are merging. Automatically, this means that you are 
      # seeing one less connected area. 
      count -= 1 
     else: 
      current = max(current, vector[i]) 
      if current == 0: 
      # If the neighboring squares are colored 0, then pick a new 
      # color. 
      current = nextToken 
      nextToken += 1 
      count += 1 

     vector[i] = current 

    return count

这里有几个电网尝试了这一点上：

gridOne = [ 
    [ True, True, False, False, False, False, True ], 
    [ True, True, False, False, False, False, True ], 
    [ True, True, False, True, True, False, True ], 
    [ True, True, False, False, True, False, True ], 
    [ True, True, False, False, False, False, True ], 
    [ False, True, False, False, False, False, True ], 
    [ False, True, True, False, False, False, True ], 
    [ True, False, True, False, False, False, True ] ] 

gridTwo = gridOne + [ 
    [ True, True, True, True, True, True, True] ] 

countConnectedAreas(gridOne, 7) # returns 4 
countConnectedAreas(gridTwo, 7) # returns 2

来源

2010-08-02 15:24:32

在网格中计算连接的点

回答

相关问题