Graph Traversal comte nuages ​​[python]

Question

Étant donné une carte du ciel 2D composée de '1 (nuages) et' 0 (ciel clair), comptez le nombre de nuages.

Un nuage est entouré d'un ciel dégagé et est formé en connectant les nuages ​​adjacents horizontalement ou verticalement. Vous pouvez supposer que les quatre bords de la skymap sont entourés d'un ciel clair.

Exemple

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

la sortie doit être

countClouds(skyMap) = 2; 

Pour

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

la sortie doit être

countClouds(skyMap) = 5. 

Answer 1

Cela peut être résolu en calculant les composants connectés directement sur la matrice de la carte du ciel. Nous pouvons utiliser la structure de données de .

Dans cet exemple, la mise en œuvre de disjoints-set (UnionFind) est tirée de 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())) 

Pour chaque entrée avec la valeur '1' nous créons un ensemble. Si elle est adjacente à une autre entrée, nous unissons les deux ensembles. À la fin, nous obtenons un ensemble d'ensembles disjoints, et chacun représente un nuage. Dans ce code, ds.parents nous donne accès aux "représentants" des nuages, donc nous pouvons dire le nombre de nuages.