Trovare blocchi in array

Question

stavo cercando su alcune domande di intervista, e mi sono imbattuto su questo:

C'è una serie m x n. Un blocco nella matrice è denotato da un 1 e uno 0 indica nessun blocco. Si suppone di trovare il numero di oggetti nell'array. Un oggetto non è altro che un insieme di blocchi che sono collegati orizzontalmente e/o verticalmente.

es

0 1 0 0 
0 1 0 0 
0 1 1 0 
0 0 0 0 
0 1 1 0 

Risposta: Ci sono 2 oggetti in questa matrice. L'oggetto forma L e l'oggetto nell'ultima riga.

Sto riscontrando problemi con un algoritmo in grado di rilevare una forma "u" (come sotto). Come dovrei avvicinarmi a questo?

0 1 0 1 
0 1 0 1 
0 1 1 1 
0 0 0 0 
0 1 1 0 

Answer 1

Questo funziona in C#

static void Main() 
    { 
     int[][] array = { new int[] { 0, 1, 0, 1 }, new int[] { 0, 1, 0, 1 }, new int[] { 0, 1, 1, 1 }, new int[] { 0, 0, 0, 0 }, new int[] { 0, 1, 1, 0 } }; 
     Console.WriteLine(GetNumber(array)); 
     Console.ReadKey(); 
    } 

    static int GetNumber(int[][] array) 
    { 
     int objects = 0; 
     for (int i = 0; i < array.Length; i++) 
      for (int j = 0; j < array[i].Length; j++) 
       if (ClearObjects(array, i, j)) 
        objects++; 
     return objects; 
    } 

    static bool ClearObjects(int[][] array, int x, int y) 
    { 
     if (x < 0 || y < 0 || x >= array.Length || y >= array[x].Length) return false; 
     if (array[x][y] == 1) 
     { 
      array[x][y] = 0; 
      ClearObjects(array, x - 1, y); 
      ClearObjects(array, x + 1, y); 
      ClearObjects(array, x, y - 1); 
      ClearObjects(array, x, y + 1); 
      return true; 
     } 
     return false; 
    } 

Answer 2

Perché non guardare solo le celle adiacenti di un determinato blocco? Inizia da una cella che ha un 1 in essa, tieni traccia delle celle che hai visitato prima e continua a cercare tra le celle adiacenti finché non trovi più un 1. Quindi spostati sulle celle che non hai ancora guardato e ripeti il ​​processo.

Answer 3

Qualcosa del genere dovrebbe funzionare:

1. mentre array ha un 1 che non è segnato:
   1. creare un nuovo oggetto
   2. creare una coda
   3. Aggiungere il 1 alla coda
   4. Mentre la coda non è vuota:
      1. ottenere il 1 in cima alla coda
      2. Mark è
      3. Aggiungi a oggetto corrente
      4. look per i suoi 4 vicini
      5. se qualcuno di loro è un 1 e non ancora segnato, aggiungerlo alla coda

Answer 4

Un approccio userebbe Flood Fill. L'algoritmo sarebbe qualcosa di simile a questo:

for row in block_array: 
    for block in row: 
     if BLOCK IS A ONE and BLOCK NOT VISITED: 
      FLOOD_FILL starting from BLOCK 

Faresti contrassegnare articoli visitati durante il processo di riempimento delle inondazioni, e tenere traccia di forme da lì.

Answer 5

Vorrei utilizzare set disgiunti (componenti collegati).

All'inizio, ogni elemento della matrice (i, j) con valore 1 è un elemento impostato autonomamente.

Quindi è possibile scorrere su ciascun elemento di matrice e per ciascun elemento (i, j) è necessario unire ogni set di posizioni adiacenti {(i + 1, j), (i-1, j), (i, j + 1), (i, j-1)} a (i, j) impostare se il suo valore è 1.

È possibile trovare un'implementazione di insiemi disgiunti a Disjoint Sets in Python

alla fine, il numero di differente set è il numero di oggetti.

Answer 6

avrei usato un disjoint-set datastructure (altrimenti noto come union-find).

In breve: per ciascun componente collegato, creare un "albero inverso" utilizzando un singolo collegamento per elemento come puntatore "padre". Seguendo i puntatori principali si troverà la radice dell'albero, che viene utilizzata per l'identificazione dei componenti (poiché è la stessa per ogni membro del componente connesso). Per unire i componenti adiacenti, rendere la radice di un componente il genitore dell'altro (che non sarà più una radice, poiché ora ha un genitore).

Due semplici ottimizzazioni rendono questa infrastruttura molto efficiente. Uno è, fai in modo che tutte le query di root "comprimano" i loro percorsi in modo che puntino direttamente alla radice - in questo modo, la query successiva richiederà solo un passaggio. L'altro è, usa sempre il "più profondo" dei due alberi come nuova radice; questo richiede il mantenimento di un punteggio di "rango" per ogni radice.

Inoltre, per rendere più efficiente la valutazione dei vicini, è possibile considerare la pre-elaborazione dell'input in base alle singole righe. In questo modo, un segmento contiguo di 1 sulla stessa riga può iniziare la vita come un singolo componente connesso ed è possibile analizzare in modo efficiente i segmenti della riga precedente in base al criterio del tuo vicino.

Answer 7

I miei due centesimi (barra) algoritmo:

1. List only the 1's. 

2. Group (collect connected ones). 

In Haskell:

import Data.List (elemIndices, delete) 

example1 = 
    [[0,1,0,0] 
    ,[0,1,0,0] 
    ,[0,1,1,0] 
    ,[0,0,0,0] 
    ,[0,1,1,0]] 

example2 = 
    [[0,1,0,1] 
    ,[0,1,0,1] 
    ,[0,1,1,1] 
    ,[0,0,0,0] 
    ,[0,1,1,0]] 

objects a ws = solve (mapIndexes a) [] where 
    mapIndexes s = 
    concatMap (\(y,xs)-> map (\x->(y,x)) xs) $ zip [0..] (map (elemIndices s) ws) 
    areConnected (y,x) (y',x') = 
    (y == y' && abs (x-x') == 1) || (x == x' && abs (y-y') == 1) 
    solve []  r = r 
    solve (x:xs) r = 
    let r' = solve' xs [x] 
    in solve (foldr delete xs r') (r':r) 
    solve' vs r = 
    let ys = filter (\y -> any (areConnected y) r) vs 
    in if null ys then r else solve' (foldr delete vs ys) (ys ++ r) 

uscita:

*Main> objects 1 example1 
[[(4,2),(4,1)],[(2,2),(2,1),(1,1),(0,1)]] 
(0.01 secs, 1085360 bytes) 

*Main> objects 1 example2 
[[(4,2),(4,1)],[(0,3),(1,3),(2,3),(2,2),(2,1),(1,1),(0,1)]] 
(0.01 secs, 1613356 bytes)