Swim in Rising Water
Ti viene fornita una griglia n × n di altezze che contiene ogni numero da 0 a n²-1 esattamente una volta. 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, senza impiegare tempo, fino a una cella che condivide un lato con la tua quando entrambe sono sommerse. 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, con la cella più alta pari a 2. Attraverso quella in basso a sinistra è 0, 3, 1, con la cella più alta pari a 3. Al tempo 2 il primo percorso è sott'acqua.
- 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 raggiungi solo la riga superiore e il 5 sotto la sua estremità; ogni via d’uscita passa per 16 o più. Girando da 16 attraverso 15, 14, 13, 12, 11 e la riga inferiore, non si sale mai oltre 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.
Per approfondire
Se le altezze potessero ripetersi e arrivare a 10^9, quale dei tuoi approcci funzionerebbe ancora 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. Sai dire se esiste un passaggio? Come cambia la risposta quandotaumenta?Un percorso ha bisogno che l'acqua copra ogni cella che lo compone, quindi il tempo richiesto da un percorso è determinato dalla sua cella più alta. Vuoi il percorso tra gli angoli la cui cella più alta sia il più bassa possibile.
Usa la ricerca binaria su
tcon un riempimento flood fill come test, oppure esegui l’algoritmo di Dijkstra con un heap minimo, in cui il tempo di una cella è il maggiore tra il tempo con cui sei arrivato e la sua altezza. Fermati quando la cella in basso a destra esce dall’heap.
Soluzione
Un percorso richiede tanto tempo quanto la sua cella più alta, perché l'acqua deve coprire ogni cella attraversata. Quindi trova il percorso tra gli angoli la cui cella più alta è la più bassa: un percorso minimo il cui costo è il massimo, non la somma. Alza il livello dell'acqua passo dopo passo, esegui una ricerca binaria sul livello oppure applica l'algoritmo di Dijkstra a quel costo.
Alza l’acqua un passo alla volta
Corretto, ma non termina sui test più grandi
Intuizione
Fissa un livello dell'acqua t. Un flood fill dall'angolo in alto a sinistra, attraverso le celle di altezza al massimo t, ti dice se l'angolo in basso a destra è raggiungibile. Inizia t dal valore più alto tra i due angoli, max(grid[0][0], grid[n-1][n-1]), perché entrambi gli angoli devono essere sommersi, e aumenta di 1 finché il flood fill non riesce a passare. L'aumento del livello dell'acqua apre solo nuove celle, quindi il primo livello che funziona è la risposta.
Ogni flood fill costa O(n²) e il livello dell'acqua può aumentare quasi n² volte: su una griglia 100 × 100, fino a 10^4 livelli × 10^4 celle, circa 10^8 visite alle celle.
Algoritmo
- Imposta
tall'altezza maggiore tra quelle dei due angoli. - Esegui un riempimento flood fill dall'angolo in alto a sinistra attraverso le celle con altezza al massimo
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 di riempimento flood fill fallisce per ogni livello inferiore alla risposta e riesce per ogni livello a partire dalla risposta. La ricerca binaria trova quel punto di svolta, tra l’angolo più alto e n²-1, in cui l’intera griglia è sott’acqua.
Nell’esempio 5 × 5, lo = 6 e hi = 24. Il livello 15 fallisce, quindi lo = 16. I livelli 20, 18, 17 e 16 riescono tutti, e la ricerca termina a 16 dopo cinque riempimenti.
Una griglia 100 × 100 ha 10^4 livelli, quindi bastano circa 14 riempimenti per determinarlo: circa 1.4 × 10^5 visite alle celle invece di 10^8.
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
Assegna a ogni percorso un costo: quello della sua cella più alta. L'algoritmo di Dijkstra funziona comunque, perché estendere un percorso a una cella di altezza h costa max(old cost, h), mai meno del costo precedente. Mantieni un min-heap di celle, con priorità basata su quel tempo, iniziando dall'angolo in alto a sinistra in grid[0][0]. 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 una vicina le assegna il tempo minimo possibile, e ogni cella entra nell'heap una sola volta.
L'heap contiene il bordo dell'area che puoi raggiungere e ogni estrazione innalza l'acqua esattamente quanto basta per arrivarci. Nell'esempio 5 × 5, le estrazioni avvengono ai tempi 0, 1, 2, 3, 4, 5, poi al cancello a 16, e l'angolo in basso a destra esce con 16.
Algoritmo
- Contrassegna la cella in alto a sinistra come visitata e inseriscila con il tempo
grid[0][0]. - Estrai la cella con il tempo minimo
t. Se è quella in basso a destra, restituiscit. - Per ogni vicina 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
- Ignorare l’altezza dell’angolo stesso. La risposta è almeno
grid[0][0]egrid[n-1][n-1]: con[[3, 0], [1, 2]]è 3. - Procedere avidamente verso il vicino più basso. Il percorso migliore potrebbe salire fino a un varco e poi fare il giro lungo, come nell’esempio 5 × 5.
- 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 il riempimento per allagamento. Un percorso tortuoso può essere lungo migliaia di celle, superando il limite di Python di 1.000 chiamate annidate.
Domande frequenti3
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. 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²) memoria.
Can Swim in Rising Water può essere risolto con la ricerca binaria?
Sì. La possibilità di attraversare al livello t cambia una sola volta, da falso a vero, in corrispondenza della risposta. La ricerca binaria su t, usando un flood fill come test, richiede circa log2(n²) riempimenti, 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 già aperte e fermati non appena i due angoli appartengono allo stesso insieme. L’altezza dell’ultima cella aperta è la risposta. Poiché ogni valore da 0 a n²-1 compare una volta, una tabella che associa ogni altezza a una cella fornisce l’ordine senza ordinare.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def swimInWater(grid):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
grid = [[0, 2], [3, 1]]
Output atteso
2