圖遍歷計數雲[蟒]

Question

給定由1（雲）和0（晴空）組成的二維網格skyMap，計算雲的數量。

雲被晴空包圍，並且通過水平或垂直連接相鄰的雲而形成。您可以假設skyMap的所有四條邊都被晴空包圍。

例

skyMap = [['0', '1', '1', '0', '1'], 
      ['0', '1', '1', '1', '1'], 
      ['0', '0', '0', '0', '1'], 
      ['1', '0', '0', '1', '1']] 

輸出應該是

countClouds(skyMap) = 2; 

對於

skyMap = [['0', '1', '0', '0', '1'], 
      ['1', '1', '0', '0', '0'], 
      ['0', '0', '1', '0', '1'], 
      ['0', '0', '1', '1', '0'], 
      ['1', '0', '1', '1', '0']] 

輸出應該是

countClouds(skyMap) = 5. 

Answer 1

這可以通過直接在天空地圖矩陣上計算連接的組件來解決。我們可以使用的數據結構。

在這個例子中，不相交集的實現（UnionFind）從here採取：

refs = [[0, 0], [-1, 0], [0, -1], [1, 0], [0, 1]] 
for i in range(len(skyMap)): 
    for j in range(len(skyMap[i])): 
     print i, j 
     for dy, dx in refs: 
      is_neighbour_valid = 0 <= (i + dy) < len(skyMap) and 0 <= (j + dx) < len(skyMap[i]) 
      if not is_neighbour_valid: 
       continue 

      current_cell, neighbour_cell = skyMap[i][j] == '1', skyMap[i + dy][j + dx] == '1' 
      if current_cell and is_neighbour_valid: 
       ds.union((i, j), (i + dy, j + dx)) 

# The number of connected components: 
print len(set(ds.parents.values())) 

對於價值'1'我們創建一組中的每個條目。如果它與另一個這樣的條目相鄰，我們將這兩個集合在一起。最後，我們得到一組不相交的集合，每個集合代表一個雲。在此代碼中，ds.parents使我們可以訪問雲的「代表」，因此我們可以知道雲的數量。