Number of Islands

Q: Qual è la complessità temporale di Number of Islands?

O(rows × cols). La scansione esamina ogni casella una volta, e ogni casella di terra entra una volta nello stack o nella coda e controlla quattro vicine. I marcatori delle caselle visitate e lo stack o la coda usano O(rows × cols) di spazio su una mappa interamente composta da terra.

Q: È meglio usare BFS o DFS per il numero di isole?

Entrambi sono corretti nello stesso tempo e spazio, perché il conteggio richiede solo che ogni casella di un'isola sia contrassegnata. La BFS con una coda non ricorre mai; la DFS è altrettanto sicura quando usa uno stack esplicito.

Q: Riesci a risolvere Number of Islands con union-find?

Sì. Inserisci ogni casella di terra nel proprio insieme e imposta il conteggio iniziale sul numero di caselle di terra. Unisci ogni coppia di caselle di terra vicine e diminuisci il conteggio di uno ogni volta che un'unione collega due insiemi diversi. Con la compressione dei cammini, il tempo è vicino a O(rows × cols).

Q: Riesci a contare le isole senza un array separato per quelle visitate?

Sì, se puoi modificare la mappa: trasforma ogni casella di terra in acqua non appena la raggiungi. Molti linguaggi non consentono di modificare le stringhe sul posto, quindi prima copi le righe in una griglia di caratteri, usando lo stesso spazio occupato dai contrassegni delle caselle già viste.

MedioGrafi

+10

Ricevi una mappa sotto forma di un elenco di stringhe della stessa lunghezza, dove '1' è una casella di terra e '0' è una casella d'acqua. Due caselle di terra appartengono alla stessa isola quando condividono un lato: in alto, in basso, a sinistra o a destra. Le caselle che si toccano solo in un angolo non sono collegate. Restituisci il numero di isole.

Funzione

numIslands(grid: string-array) → integer

gridstring-array: la mappa, una stringa per riga
Restituisceinteger: il numero di isole

Vincoli

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
Ogni riga ha la stessa lunghezza.
Ogni carattere è '0' oppure '1'.

Esempi

Input: grid = ["11000", "11000", "00100", "00011"]
Output: 3
Spiegazione: I quattro quadrati in alto a sinistra formano un’isola. Il quadrato centrale della terza riga li tocca solo in un angolo, quindi costituisce una seconda isola. La coppia in basso a destra è la terza.

Per approfondire

LAND ora appare un quadrato alla volta su una mappa d'acqua. Riesci a comunicare il numero di isole dopo ogni nuovo quadrato senza esaminare di nuovo l'intera mappa?

Soluzione

Considera ogni casella di terra come un nodo collegato alle caselle di terra adiacenti: un'isola è un'unica porzione connessa. Esamina la mappa e, ogni volta che raggiungi una casella di terra che non hai ancora visto, conta una nuova isola e riempila con una ricerca flood fill, contrassegnando ogni sua casella in modo che la scansione non la conti di nuovo.

Riempimento per inondazione con uno stack esplicito (DFS)

Intuizione

Una casella di terra non contrassegnata non può appartenere a un’isola che hai già contato, perché il conteggio contrassegna tutta l’isola. Quindi dà inizio a una nuova isola. Uno stack che gestisci tu stesso contrassegna il resto: ogni casella che estrai inserisce nello stack le caselle di terra adiacenti non contrassegnate e, quando lo stack è vuoto, l’intera isola è contrassegnata.

Il tuo stack è importante perché un riempimento ricorsivo può raggiungere una profondità di 22,500 chiamate su una mappa di 150 × 150 composta interamente da terra. Ogni casella viene inserita nello stack al massimo una volta e controlla quattro caselle adiacenti, quindi il tempo è O(rows × cols). I contrassegni e lo stack occupano O(rows × cols) spazio quando la mappa è interamente composta da terra.

Algoritmo

Crea un contrassegno di visita per ogni casella e imposta il conteggio a 0.
Esamina ogni casella, saltando l'acqua e le caselle già visitate.
Su una casella di terra non visitata, aggiungi 1 al conteggio, contrassegna la casella e inseriscila in uno stack.
Finché lo stack non è vuoto, estrai una casella e inserisci nello stack ogni casella adiacente all'interno della mappa che sia terra e non visitata, contrassegnandola prima di inserirla.
Restituisci il conteggio al termine dell'esame.

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1' or seen[r][c]:
                continue
            # Land that no island has claimed yet: a new island.
            count += 1
            seen[r][c] = True
            stack = [(r, c)]
            while stack:
                i, j = stack.pop()
                for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
                        # Mark on push, so no square enters the stack twice.
                        seen[ni][nj] = True
                        stack.append((ni, nj))
    return count

Riempimento a inondazione con una coda (BFS)

Intuizione

Il conteggio funziona allo stesso modo; cambia solo l’ordine di visita. Una coda preleva le caselle dall’inizio e aggiunge in fondo le caselle di terra adiacenti non contrassegnate, quindi visita l’isola ad anelli: la prima casella, poi tutte le caselle a un passo di distanza, poi quelle a due passi di distanza. Ogni casella viene comunque visitata una sola volta, in tempo e spazio O(rows × cols).

L’ordine ad anelli fornisce la distanza di ogni casella dall’inizio, quindi lo stesso ciclo risponde alle domande sul percorso più breve in una griglia con un numero in più per casella.

Algoritmo

Crea un contrassegno di visita per ogni casella e imposta il conteggio su 0.
Esamina ogni casella, saltando l’acqua e le caselle già visitate.
Sulla terra non ancora visitata, aggiungi 1 al conteggio, contrassegna la casella e inseriscila in una coda vuota.
Finché la coda contiene caselle, prendine una dall’inizio e aggiungi in fondo ogni casella adiacente all’interno della mappa che sia terra non ancora visitata, contrassegnandola mentre la aggiungi.
Al termine dell’esame, restituisci il conteggio.

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1' or seen[r][c]:
                continue
            count += 1
            seen[r][c] = True
            stack = [(r, c)]
            while stack:
                i, j = stack.pop()
                for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
                        seen[ni][nj] = True
                        stack.append((ni, nj))
    return count

Trappole e casi limite

Contrassegnare una casella quando la estrai dallo stack o dalla coda invece di farlo quando la inserisci. La stessa casella viene quindi aggiunta più volte.
Confrontare una casella con il numero 1 invece che con il carattere '1'. Ogni riga è una stringa, quindi ogni casella è un carattere.
Leggere una casella vicina prima di verificare 0 ≤ row < rows e 0 ≤ col < cols. Una casella di terra sul bordo legge quindi una posizione fuori dalla mappa.
Scrivere il riempimento in modo ricorsivo. Per impostazione predefinita, Python si ferma dopo 1.000 chiamate e altri linguaggi possono causare un overflow dello stack su un'isola grande.
Estrarre il primo elemento di una lista Python con pop(0), operazione che richiede un tempo proporzionale alla lunghezza della lista. Usa collections.deque e popleft().

Domande frequenti4

Qual è la complessità temporale di Number of Islands?

O(rows × cols). La scansione esamina ogni casella una volta, e ogni casella di terra entra una volta nello stack o nella coda e controlla quattro vicine. I marcatori delle caselle visitate e lo stack o la coda usano O(rows × cols) di spazio su una mappa interamente composta da terra.

È meglio usare BFS o DFS per il numero di isole?

Entrambi sono corretti nello stesso tempo e spazio, perché il conteggio richiede solo che ogni casella di un'isola sia contrassegnata. La BFS con una coda non ricorre mai; la DFS è altrettanto sicura quando usa uno stack esplicito.

Riesci a risolvere Number of Islands con union-find?

Sì. Inserisci ogni casella di terra nel proprio insieme e imposta il conteggio iniziale sul numero di caselle di terra. Unisci ogni coppia di caselle di terra vicine e diminuisci il conteggio di uno ogni volta che un'unione collega due insiemi diversi. Con la compressione dei cammini, il tempo è vicino a O(rows × cols).

Riesci a contare le isole senza un array separato per quelle visitate?

Sì, se puoi modificare la mappa: trasforma ogni casella di terra in acqua non appena la raggiungi. Molti linguaggi non consentono di modificare le stringhe sul posto, quindi prima copi le righe in una griglia di caratteri, usando lo stesso spazio occupato dai contrassegni delle caselle già viste.

def numIslands(grid):
    # Scrivi il codice qui

Test #1

Test #2

Argomento

grid = ["11000", "11000", "00100", "00011"]

Output atteso