Rotting Oranges

+10

Ricevi una griglia come elenco di righe della stessa lunghezza. Ogni cella è 0 (vuota), 1 (un’arancia fresca) o 2 (un’arancia marcia). Ogni minuto, ogni arancia fresca che condivide un lato con un’arancia marcia, sopra, sotto, a sinistra o a destra, diventa marcia. Restituisci il numero di minuti necessari affinché non rimangano arance fresche, oppure -1 se alcune arance fresche non possono mai marcire. Una griglia senza arance fresche all’inizio richiede 0 minuti.

Funzione

orangesRotting(grid: integer-2d-array) → integer

gridinteger-2d-array: la griglia, un elenco di 0, 1 e 2 per riga
Restituisceinteger: i minuti fino a quando nessuna arancia è più fresca, oppure -1 se ciò non accade mai

Vincoli

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
Ogni riga ha la stessa lunghezza.
Ogni grid[i][j] è 0, 1 oppure 2.

Esempi

Input: grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]
Output: 6
Spiegazione: Indicando le celle come (riga, colonna), la muffa parte da (0,0) e segue l’unico percorso: (0,1) al minuto 1, (0,2) e (1,1) al minuto 2, (2,1) al minuto 3, (2,0) e (2,2) al minuto 4, (2,3) al minuto 5. L’arancia in (1,3) tocca solo (2,3), quindi è l’ultima a marcire, al minuto 6.

+21 test nascosti all’invio

Per approfondire

Supponiamo che ogni arancia fresca impieghi un numero diverso di minuti a marcire una volta che un'arancia vicina è marcia. Come troveresti allora il tempo di completamento?

Soluzione

La decomposizione parte contemporaneamente da ogni arancia marcia e si propaga di una cella al minuto, quindi la risposta è una distanza: quanti passi separano l’arancia fresca più lontana dall’arancia marcia più vicina. La ricerca in ampiezza misura esattamente questo, se inserisci tutte le arance marce nella coda prima di iniziare e la elabori un livello alla volta, un minuto alla volta.

Simula minuto per minuto

Corretto, ma non termina sui test più grandi

Intuizione

Fai ciò che dice la storia. Ogni minuto, esamina l'intera griglia ed elenca ogni arancia fresca che tocca un'arancia marcia. Poi fai marcire tutte quelle arance, aggiungi uno all'orologio ed esamina di nuovo la griglia. Fermati quando una scansione non trova nulla da far marcire. Se a quel punto nella griglia è ancora presente un'arancia fresca, la marcescenza non potrà mai raggiungerla: restituisci -1.

Prima elenca, poi fai marcire. Se fai marcire un'arancia nel mezzo di una scansione, una cella esaminata più avanti nella stessa scansione la vede come marcia e marcisce a sua volta, quindi la marcescenza attraversa di corsa diverse celle in un minuto e il tempo risulta troppo basso.

È corretto, ma ogni minuto richiede una scansione completa delle righe × colonne della griglia, e il numero di minuti può avvicinarsi al numero di celle. In una griglia di 150 × 150 le cui arance fresche formano un unico percorso tortuoso con la marcescenza all'inizio, la marcescenza richiede 11,324 minuti: 11,324 scansioni di 22,500 celle, circa 2.5 × 10^8 controlli di celle, quasi tutti su celle che non possono cambiare.

Algoritmo

Imposta i minuti a 0.
Esamina la griglia ed elenca ogni arancia fresca che ha una vicina marcia.
Se l'elenco è vuoto, fermati. Altrimenti fai marcire ogni arancia elencata, aggiungi 1 ai minuti e fai una nuova scansione.
Restituisci -1 se rimane un'arancia fresca, altrimenti restituisci i minuti.

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    minutes = 0
    while True:
        # Find every fresh orange that touches a rotten one right now.
        to_rot = []
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != 1:
                    continue
                for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 2:
                        to_rot.append((r, c))
                        break
        if not to_rot:
            break
        # Rot them only after the scan, so the rot moves one step a minute.
        for r, c in to_rot:
            grid[r][c] = 2
        minutes += 1
    for row in grid:
        if 1 in row:
            return -1
    return minutes

Ricerca BFS multi-sorgente per livelli

Intuizione

La scansione spreca tempo sulle celle lontane dall'azione. Le uniche arance che possono marcire al minuto t+1 sono le vicine fresche delle arance marcite al minuto t. Quindi tieni in una coda esattamente quelle: la frontiera del marciume.

Inizia la coda con tutte le arance marce al minuto 0, tutte insieme. Questa è la parte multi-sorgente. Un'arancia fresca marcisce al minuto pari alla sua distanza dall'arancia marcia più vicina, e una ricerca in ampiezza avviata da tutte le sorgenti raggiunge ogni cella prima partendo dalla sorgente più vicina. Una sola ricerca fa il lavoro di una ricerca per sorgente, più il calcolo del minimo.

Poi procedi per livelli. All'inizio di un minuto la coda contiene k arance, quelle marcite nell'ultimo minuto. Estrai esattamente k elementi dall'inizio; per ciascuno, fai marcire le sue vicine fresche e aggiungile alla fine. Quando hai elaborato tutti i k elementi, è passato un minuto e la coda contiene la frontiera successiva. Nel primo esempio i livelli sono {(0,0)}, {(0,1)}, {(0,2), (1,1)}, {(2,1)}, {(2,0), (2,2)}, {(2,3)}, {(1,3)}: sei passi dopo l'inizio, quindi sei minuti.

Conta le arance fresche una volta all'inizio e diminuisci il conteggio ogni volta che un'arancia marcisce. Fermati non appena raggiunge 0, altrimenti l'ultimo livello aggiungerebbe un minuto in cui non marcisce nulla, e restituisci -1 se la coda si svuota mentre il conteggio è maggiore di 0. Ogni cella entra in coda al massimo una volta e controlla quattro vicine, quindi il lavoro è O(rows × cols).

Algoritmo

Metti tutte le arance marce in una coda e conta quelle fresche.
Imposta i minuti a 0. Mentre la coda non è vuota e restano arance fresche, aggiungi 1 ai minuti e annota la dimensione k della coda.
Prendi k arance dalla testa della coda. Per ogni vicina fresca all'interno della griglia, contrassegnala come marcia, diminuisci il conteggio delle arance fresche e aggiungila alla coda.
Quando il ciclo termina, restituisci i minuti se il conteggio delle arance fresche è 0, altrimenti -1.

from collections import deque


def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    # Every orange that is rotten at minute 0 starts in the queue.
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh > 0:
        minutes += 1
        # The queue holds exactly the oranges that went rotten last minute.
        # Rot their fresh neighbours; those become the next minute's queue.
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
    return minutes if fresh == 0 else -1

Trappole e casi limite

La maggior parte delle risposte sbagliate qui differisce di un minuto, oppure deriva dall’avviare la ricerca dal punto sbagliato.

Contare un minuto per l’ultimo livello. Se il ciclo continua finché la coda non è vuota, l’ultimo passaggio non fa marcire nulla e aggiunge comunque 1. Fermati non appena non restano arance fresche.
Cercare partendo da ogni arancia marcia, una alla volta. La prima ricerca raggiunge tutte le arance che incontra usando il proprio orologio, quindi due fonti che dovrebbero incontrarsi a metà danno un tempo troppo alto: [[2, 1, 1, 1, 1, 1, 1, 2]] richiede 3 minuti, non 6.
Far marcire le arance durante la scansione nella versione minuto per minuto. Una cella visitata più avanti nella stessa scansione le vede quindi come marce, e il marciume attraversa diverse celle in un minuto.
Restituire -1 perché non ci sono arance marce. Se non ci sono nemmeno arance fresche, non deve succedere nulla: [[0]] restituisce 0. La risposta è -1 solo quando alcune arance fresche non marciscono mai.
Segnare un’arancia come marcia quando la estrai dalla coda invece di quando la inserisci. Un’arancia accanto a due arance marce viene quindi inserita due volte e il conteggio delle arance fresche scende sotto zero.
Ricerca in profondità. Segue un percorso fino in fondo, quindi la prima volta che raggiunge un’arancia non dice nulla sul minuto in cui quell’arancia marcisce.

Domande frequenti4

Qual è la complessità temporale del problema delle arance marce?

O(rows × cols) con la ricerca in ampiezza. La prima scansione esamina ogni cella una volta, e ogni arancia entra nella coda al massimo una volta e controlla quattro vicine. Nel caso peggiore, la coda occupa uno spazio O(rows × cols): una griglia piena di arance marce.

Perché usare BFS e non DFS per Rotting Oranges?

La ricerca in ampiezza visita le celle in ordine di distanza dall’inizio, e qui la distanza corrisponde al tempo: il livello k della ricerca è esattamente l’insieme delle arance che marciscono al minuto k. La ricerca in profondità può raggiungere una cella seguendo un lungo percorso alternativo prima di trovare il percorso più breve, quindi dovrebbe rivisitare le celle ogni volta che ne trova uno più breve.

Che cos'è la BFS multi-sorgente?

Una ricerca in ampiezza che inizia con diverse celle nella coda a distanza 0 invece che con una sola. In un unico passaggio assegna a ogni cella la distanza dalla sorgente più vicina, ottenendo lo stesso risultato di una ricerca per ogni sorgente prendendo il minimo, ma al costo di una sola ricerca. Si usa per qualsiasi domanda del tipo «distanza dalla X più vicina» su una griglia.

Riesci a risolvere Rotting Oranges senza modificare la griglia?

Sì. Tieni un array separato per le celle visitate e controllalo invece di scrivere 2 nella griglia. Questo richiede O(rows × cols) di memoria aggiuntiva, che potrebbe comunque servire alla coda. Nei linguaggi che passano la griglia per riferimento, scriverci dentro modifica anche la griglia del chiamante, cosa di cui un intervistatore potrebbe chiederti conto.

Python

def orangesRotting(grid):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]

Atteso