Swim in Rising Water
Ti viene data una griglia n × n di altezze che contiene ogni numero da 0 a n²-1 esattamente una volta, sotto forma di un elenco di righe. Inizia a piovere al tempo 0 e, al tempo t, l’acqua raggiunge ovunque l’altezza t, quindi ogni cella con altezza pari o inferiore a t è sommersa. Parti dalla cella in alto a sinistra. Puoi nuotare da una cella a una cella che condivide un lato con essa quando entrambe sono sommerse, e nuotare non richiede tempo. Restituisci il tempo minimo in cui puoi raggiungere la cella in basso a destra.
Funzione
- gridinteger-2d-array
- le altezze, come un elenco di n righe di n numeri
- Restituisceinteger
- il momento più precoce in cui puoi raggiungere la cella in basso a destra
Vincoli
n == grid.length == grid[i].length1 ≤ n ≤ 1000 ≤ grid[i][j] ≤ n²-1- Ogni valore da 0 a
n²-1compare esattamente una volta.
Esempi
- Input
- grid = [[0, 2], [3, 1]]
- Output
- 2
- Spiegazione
- Attraverso la cella in alto a destra, il percorso è 0, 2, 1 e la cella più alta è 2. Attraverso la cella in basso a sinistra, il percorso è 0, 3, 1, con la cella più alta pari a 3. Al tempo 2 il primo percorso è sott'acqua, quindi la risposta è 2.
- Input
- grid = [[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [12, 13, 14, 15, 16], [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]]
- Output
- 16
- Spiegazione
- Al tempo 15 puoi raggiungere la riga superiore e il 5 sotto la sua estremità, ma ogni via d’uscita da quell’area passa per 16 o più. Scendendo dritto lungo il lato destro incontri 16 e poi 20. Svoltando a sinistra al 16 e facendo il giro passando per 15, 14, 13, 12, 11 e tornando indietro lungo la riga inferiore, non si supera mai 16, quindi la risposta è 16.
- Input
- grid = [[3, 0], [1, 2]]
- Output
- 3
- Spiegazione
- La cella iniziale ha altezza 3, quindi non puoi trovarti al suo interno né lasciarla prima del tempo 3. A quel punto, l’intera griglia è sott’acqua.
+13 test nascosti all’invio
Per approfondire
Se le altezze potessero ripetersi e arrivare a 10^9, quale dei tuoi approcci continuerebbe a funzionare senza modifiche e su cosa faresti una ricerca binaria?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Supponiamo che tu conosca il livello dell’acqua
t. Riesci a dire se esiste un passaggio? Come cambia la risposta man mano chetaumenta?Un percorso ha bisogno che l'acqua copra ogni cella su di esso, quindi il tempo necessario a un percorso è determinato dalla cella più alta. Vuoi il percorso tra gli angoli la cui cella più alta sia il più bassa possibile.
Puoi eseguire una ricerca binaria su
tusando un riempimento per inondazione come test, oppure eseguire l'algoritmo di Dijkstra con un heap minimo, in cui il tempo di una cella è il maggiore tra il tempo con cui ci sei arrivato e la sua altezza. Fermati quando la cella in basso a destra esce dall'heap.
Soluzione
Il tempo necessario per un percorso è determinato dalla sua cella più alta, perché l’acqua deve coprire ogni cella che attraversi. Quindi il compito consiste nel trovare il percorso tra gli angoli la cui cella più alta sia il più bassa possibile: un percorso minimo in cui il costo del percorso è il suo valore massimo, non la sua somma. Puoi alzare il livello dell’acqua un passo alla volta e fare una verifica, eseguire una ricerca binaria sul livello dell’acqua usando la stessa verifica oppure usare l’algoritmo di Dijkstra considerando la cella più alta come costo.
Alza l’acqua un passo alla volta
Corretto, ma non termina sui test più grandi
Intuizione
Fissa un livello dell'acqua t. Le celle che puoi raggiungere sono quelle con altezza al massimo t collegate alla partenza attraverso celle di questo tipo. Una visita flood fill dall'angolo in alto a sinistra le individua: inserisci la cella di partenza, estrai una cella e inserisci ogni vicina non visitata con altezza al massimo t. Se l'angolo in basso a destra viene visitato, il tempo t è sufficiente.
La risposta è il più piccolo t per cui la visita flood fill riesce ad arrivare a destinazione. Non può essere inferiore al valore dell'angolo più alto, max(grid[0][0], grid[n-1][n-1]), perché entrambi gli angoli devono essere sommersi. Parti da quel valore e aggiungi 1 finché la visita non riesce. Il primo livello che funziona è la risposta, perché l'acqua che sale apre celle e non ne chiude mai: un livello che funziona continua a funzionare.
Ogni test richiede O(n²) operazioni e l'acqua potrebbe salire quasi n² volte prima di raggiungere la destinazione. Su una griglia 100 × 100 si arriva fino a 10^4 livelli × 10^4 celle, circa 10^8 visite di celle. Nei test più grandi gli angoli contengono 0 e 1 e le risposte sono comprese tra 4,950 e 9,998, quindi vengono eseguite migliaia di visite flood fill complete prima che si trovi la risposta.
Algoritmo
- Imposta
tall'altezza maggiore tra quelle dei due angoli. - Esegui il riempimento a cascata dall'angolo in alto a sinistra attraverso le celle con altezza al massimo pari a
t, usando uno stack esplicito e un contrassegno di visita per ogni cella. - Se il riempimento raggiunge l'angolo in basso a destra, restituisci
t. - Altrimenti aggiungi 1 a
ted esegui di nuovo il riempimento.
def canReach(grid, t):
# True when you can swim from the top left to the bottom right with the water at height t.
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
stack = [(0, 0)]
while stack:
r, c = stack.pop()
if r == n - 1 and c == n - 1:
return True
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
seen[nr][nc] = True
stack.append((nr, nc))
return False
def swimInWater(grid):
n = len(grid)
# You cannot finish before the water covers both corners.
t = max(grid[0][0], grid[n - 1][n - 1])
# Raise the water one step at a time until a way through opens.
while not canReach(grid, t):
t += 1
return tRicerca binaria sul livello dell’acqua
Intuizione
Il test del primo approccio ha una forma utile. Fallisce per ogni livello inferiore alla risposta e ha successo per ogni livello a partire dalla risposta. Una domanda con risposta sì o no che cambia una sola volta, da no a sì, è ciò che la ricerca binaria trova con un numero logaritmico di tentativi.
Cerca tra lo, l'angolo più alto, e hi = n²-1, la cella più alta, dove l'intera griglia è sott'acqua e il test deve avere successo. Prova il livello centrale. Se riesci a passare, la risposta è al massimo mid, quindi imposta hi = mid; altrimenti è superiore a mid, quindi imposta lo = mid + 1. Quando i due estremi coincidono, quel livello è la risposta.
Nell'esempio 5 × 5 lo = 6 e hi = 24. Il livello 15 fallisce, perché l'area superiore è chiusa, quindi lo = 16. I livelli 20, 18, 17 e 16 hanno tutti successo, abbassando hi a 16, e la ricerca termina a 16 dopo cinque riempimenti di regioni.
Una griglia 100 × 100 ha 10^4 livelli, quindi circa 14 test sono sufficienti per determinarlo, ciascuno O(n²): circa 1.4 × 10^5 visite alle celle invece di 10^8. Mantieni iterativo il riempimento delle regioni. Un test impegnativo è un corridoio tortuoso lungo circa 5,000 celle, molto più profondo del limite di 1,000 chiamate annidate di Python.
Algoritmo
- Imposta
loall'altezza dell'angolo più alto ehian²-1. - Mentre
lo < hi, calcolamid = (lo + hi) / 2, arrotondato per difetto. - Esegui il riempimento a livello
mid. Se raggiunge l'angolo in basso a destra, impostahi = mid; altrimenti impostalo = mid + 1. - Restituisci
lo.
def canReach(grid, t):
# True when you can swim from the top left to the bottom right with the water at height t.
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
stack = [(0, 0)]
while stack:
r, c = stack.pop()
if r == n - 1 and c == n - 1:
return True
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
seen[nr][nc] = True
stack.append((nr, nc))
return False
def swimInWater(grid):
n = len(grid)
# The answer lies between the higher corner and the highest cell.
lo = max(grid[0][0], grid[n - 1][n - 1])
hi = n * n - 1
# canReach is false below the answer and true from it on: find the first true.
while lo < hi:
mid = (lo + hi) // 2
if canReach(grid, mid):
hi = mid
else:
lo = mid + 1
return loDijkstra sulla cella più alta del percorso
Intuizione
Considera la griglia come un grafo e assegna a ogni percorso un costo: la sua cella più alta, non la somma dei suoi passaggi. L’algoritmo di Dijkstra funziona comunque con questo costo, perché estendere un percorso non lo rende mai più economico. Il costo del percorso più lungo è max(old cost, new height), mai inferiore al costo precedente, ed è proprio questa la proprietà di cui Dijkstra ha bisogno.
Mantieni un min-heap di celle, con priorità pari al loro tempo: la cella più alta sul miglior percorso trovato per raggiungerle. Inizia dall’angolo in alto a sinistra al tempo grid[0][0]. Estrai la cella con il tempo più piccolo t; ogni vicino che non hai ancora visto riceve il tempo max(t, its height). Quando l’angolo in basso a destra esce dall’heap, il suo tempo è la risposta.
Puoi contrassegnare una cella come visitata la prima volta che la inserisci. Le celle escono dall’heap in ordine di tempo, quindi la prima cella che raggiunge un vicino ha il tempo più piccolo tra tutte quelle che lo raggiungeranno, e il tempo assegnato a quel vicino è il migliore possibile. Un percorso successivo arriverà con un tempo almeno altrettanto grande. Quindi ogni cella entra nell’heap una sola volta, con il suo tempo definitivo.
È così che sale l’acqua, passo dopo passo. L’heap contiene il confine dell’area che puoi raggiungere, ed estrarre la cella più bassa significa lasciare salire l’acqua esattamente quanto basta per raggiungerla. Nell’esempio 5 × 5, le estrazioni avvengono ai tempi 0, 1, 2, 3, 4, 5, poi al cancello a 16. Dopodiché, ogni cella lungo il percorso alternativo riceve il tempo 16, e l’angolo in basso a destra esce dall’heap con il tempo 16, prima di qualsiasi cella più alta.
Ognuna delle n² celle viene inserita ed estratta al massimo una volta, con costo O(log n) per operazione, quindi il tempo è O(n² log n) e la ricerca si interrompe non appena viene estratto il bersaglio.
Algoritmo
- Contrassegna l'angolo in alto a sinistra come visitato e inseriscilo con il tempo
grid[0][0]. - Estrai la cella con il tempo più piccolo
t. Se è quella in basso a destra, restituiscit. - Per ogni cella adiacente non ancora visitata, contrassegnala e inseriscila con il tempo
max(t, its height). - Ripeti dal passaggio 2.
import heapq
def swimInWater(grid):
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
# (time, row, col): the time is the highest cell on the best path found to that cell.
heap = [(grid[0][0], 0, 0)]
while True:
t, r, c = heapq.heappop(heap)
# Cells leave the heap in order of time, so this is the earliest you can be here.
if r == n - 1 and c == n - 1:
return t
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc]:
# Reached for the first time from the cell with the smallest time:
# no later route can arrive earlier, so mark it now.
seen[nr][nc] = True
heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
Trappole e casi limite
La maggior parte delle risposte sbagliate dipende da un angolo dimenticato, da un’altezza sommata invece di considerare il massimo oppure da una ricerca che si impegna troppo presto.
- Ignorare l’altezza della cella di partenza. Non puoi trovarti nell’angolo in alto a sinistra prima che sia sott’acqua, quindi la risposta è almeno
grid[0][0]. Con[[3, 0], [1, 2]]la risposta è 3. - Ignorare l’altezza della cella di destinazione. Anche l’angolo in basso a destra deve essere sott’acqua, quindi la risposta è almeno
grid[n-1][n-1]. - Procedere in modo greedy verso il vicino più basso della cella corrente. Il percorso migliore potrebbe salire fino a un passaggio e poi fare un lungo giro, come nell’esempio 5 × 5. Solo una ricerca lungo tutto il bordo dell’area raggiunta permette di trovarlo.
- Sommare le altezze lungo il percorso, come in un normale percorso più breve. Il nuovo tempo è
max(t, height), nont + height. - Usare la ricorsione per riempire l’area. Un percorso tortuoso può essere lungo migliaia di celle, superando il limite di Python di 1.000 chiamate annidate.
- Spostarsi in diagonale. Puoi nuotare solo verso una cella che condivide un lato con la tua.
Domande frequenti4
Qual è la complessità temporale di Swim in Rising Water?
O(n² log n) con l'algoritmo di Dijkstra: ciascuna delle n² celle viene inserita ed estratta al massimo una volta da un heap con fino a n² elementi. La ricerca binaria sul livello dell'acqua ha lo stesso limite, circa log2(n²) riempimenti d'acqua, ciascuno di O(n²). Entrambi usano O(n²) di memoria per i contrassegni delle celle visitate e per l'heap o lo stack.
Perché l'algoritmo di Dijkstra funziona quando il costo è quello della cella più alta?
Dijkstra richiede una proprietà: estendere un percorso non ne riduce mai il costo. Qui il nuovo costo è max(t, height), che non è mai inferiore a t, quindi la proprietà è soddisfatta. Per questo, la prima volta che una cella esce dall’heap, il suo tempo è definitivo e puoi fermarti al bersaglio.
Si può risolvere Can Swim in Rising Water con la ricerca binaria?
Sì. La possibilità di attraversare la griglia al livello t è falsa per ogni livello inferiore alla risposta e vera a partire dalla risposta. La ricerca binaria su t, usando un riempimento per diffusione come test, trova la risposta in circa log2(n²) test: 14 per una griglia di 100 × 100.
Union-find può risolvere Swim in Rising Water?
Sì. Apri le celle in ordine di altezza, unisci ogni nuova cella alle celle vicine aperte e fermati non appena quella in alto a sinistra e quella in basso a destra si trovano nello stesso insieme. L’altezza dell’ultima cella che hai aperto è la risposta. Poiché la griglia contiene una volta ciascun valore da 0 a n²-1, una tabella che associa l’altezza alla cella fornisce l’ordine di apertura senza ordinare.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def swimInWater(grid):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
grid = [[0, 2], [3, 1]]
Atteso
2