Per questo è disponibile un algoritmo predefinito: riempimento flood
L'idea è semplicemente di avviare una ricerca (DFS o BFS) da qualsiasi spazio vuoto e contrassegnarlo. Se vuoi essere in grado di distinguere la camera per ogni cella, puoi contrassegnarla con un numero di camera e un numero di dimensione, mentre quest'ultimo si incrementa durante la ricerca. Una volta terminata la ricerca a causa del riempimento completo di una camera, si conoscono le dimensioni in base al numero di dimensioni più elevato scritto durante la ricerca.
Quindi cerchi tutte le celle non marcate e non a muro e inizia un nuovo riempimento da lì con il numero di camera successivo e il numero di dimensione 1 di nuovo.
Il tuo normale algoritmo di ricerca della griglia è fondamentalmente il punto di partenza per trovare le celle libere per l'algoritmo di riempimento. Una volta che le celle sono marcate, si continua semplicemente con la stessa ricerca della griglia per cercare una cella non contrassegnata come al solito.
L'algoritmo di riempimento di piena prende il nome dalle sue origini iniziali in strumenti di disegno basati su pixel, in cui è stata la base per gli strumenti di riempimento a benna, che riempiono un'area con il colore di sfondo corrente. La pagina wikipedia collegata sopra contiene una bella gif animata per visualizzare il processo. Gli unici adattamenti per questo problema sono che è necessario impostare un numero di dimensione invece di un colore e guardare i muri, oltre a quello che si può prendere l'implementazione dello pseudocodice fornita nella pagina collegata. Ma potresti anche farti da solo, poiché è una ricerca semplice.
Non importa se effettui una ricerca in profondità o una ricerca in ampiezza. Se implementi DFS (non-tail) in modo ricorsivo e hai una matrice enorme, potresti finire nei guai con le dimensioni dello stack. In tal caso, l'investimento nello spazio di BFS potrebbe essere preferibile. Lo pseudo-codice per entrambe le varianti è riportato nella pagina di wikipedia.
Nota: la pagina di wikipedia ha già un bell'esempio sul problema di quando c'è un "buco" tra le camere. In questa descrizione del problema, non è spiegato correttamente cosa sia una 'connessione'. In altre parole, dalla descrizione non si sa se è necessario eseguire il flood a 4 o 8 vie, dove quest'ultimo consente di effettuare connessioni attraverso muri posizionati in diagonale, che condividono un angolo, ma non un bordo. Il buonsenso imporrà comunque un'inondazione a 4 vie, dato che la gente di solito non considera i portali matematicamente puntiformi nei loro castelli.
