グラフ巡回カウント雲[python]

Question

'1（雲）と' 0（晴天）からなる2DグリッドskyMapがある場合、雲の数を数えます。

雲は澄んだ空に囲まれ、隣接する雲を水平または垂直に接続することで形成されます。 skyMapの4つのエッジはすべて、澄んだ空に囲まれていると仮定できます。出力があるべき

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']] 

について

例

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

を出力しなければならない

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'有する各エントリについて。そのようなエントリに隣接している場合は、2つのセットを結合します。最後に、不連続な集合のセットを取得し、それぞれが雲を表します。このコードでは、ds.parentsは雲の「代表」にアクセスできるので、雲の数を知ることができます。