在網格中計算連接的點

我有一個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

在網格中計算連接的點

回答

相關問題