Number of Islands

Una mappa arriva come un elenco di righe della stessa lunghezza. Ogni carattere è 1, una casella di terra, oppure 0, una casella d'acqua. Due caselle di terra appartengono alla stessa isola quando una si trova direttamente sopra, sotto, a sinistra o a destra dell'altra. Le caselle che si toccano solo in un angolo non sono collegate.

Prendi la mappa ["11000", "11000", "00100", "00011"]:

• le quattro caselle di terra nell'angolo in alto a sinistra formano un'isola,
• la singola casella nella riga centrale è una seconda isola, poiché tocca la prima solo in un angolo,
• le due caselle in basso a destra formano una terza isola.

Quindi la mappa contiene 3 isole.

La mappa è in realtà un grafo: ogni casella di terra è un nodo e un arco collega due caselle di terra che condividono un lato. Contare le isole significa contare le componenti connesse di quel grafo. Ogni volta che trovi una casella di terra che non hai ancora visitato, hai trovato una nuova isola e la esplori tutta prima di proseguire.

Scrivi una funzione chiamata numIslands che riceve grid, un elenco di stringhe composte da 1 (terra) e 0 (acqua), e restituisce il numero di isole. Un’isola è un gruppo di caselle di terra collegate in alto, in basso, a sinistra o a destra.

Per esempio, ["01110", "01000", "00011", "11001"] restituisce 3: la forma nelle righe superiori, il gruppo a destra e la coppia nell’angolo in basso a sinistra.

Vincoli: 1 <= numero di righe, numero di colonne <= 150. Tutte le righe hanno la stessa lunghezza.