Swim in Rising Water
Du erhältst ein n × n-Raster mit Höhen, das jede Zahl von 0 bis n²-1 genau einmal enthält. Zum Zeitpunkt t steht das Wasser überall auf der Höhe t, sodass jede Zelle mit einer Höhe von höchstens t unter Wasser ist. Du startest in der Zelle oben links. Du kannst ohne Zeitverlust zu einer Zelle schwimmen, die eine Seite mit deiner Zelle teilt, wenn beide unter Wasser sind. Gib den frühesten Zeitpunkt zurück, zu dem du dich in der Zelle unten rechts befinden kannst.
Funktion
- gridinteger-2d-array
- die Höhen als Liste aus n Zeilen mit jeweils n Zahlen
- Gibt zurückinteger
- der früheste Zeitpunkt, zu dem du die Zelle unten rechts erreichen kannst
Einschränkungen
n == grid.length == grid[i].length1 ≤ n ≤ 1000 ≤ grid[i][j] ≤ n²-1- Jeder Wert von 0 bis
n²-1kommt genau einmal vor.
Beispiele
- Eingabe
- grid = [[0, 2], [3, 1]]
- Ausgabe
- 2
- Erklärung
- Durch die Zelle oben rechts verläuft die Route 0, 2, 1, wobei die höchste Zelle 2 ist. Durch die Zelle unten links verläuft sie 0, 3, 1, wobei die höchste Zelle 3 ist. Zum Zeitpunkt 2 liegt die erste Route unter Wasser.
- Eingabe
- 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]]
- Ausgabe
- 16
- Erklärung
- Zum Zeitpunkt 15 erreichst du nur die oberste Reihe und die 5 unter ihrem Ende; jeder Weg hinaus führt über 16 oder mehr. Wenn du von 16 aus über 15, 14, 13, 12, 11 und die unterste Reihe herumgehst, kommst du nie über 16 hinaus.
- Eingabe
- grid = [[3, 0], [1, 2]]
- Ausgabe
- 3
- Erklärung
- Die Startzelle liegt auf Höhe 3, daher kannst du dich vor Zeitpunkt 3 nicht in ihr befinden und sie auch nicht verlassen. Bis dahin steht das gesamte Raster unter Wasser.
Weiterführende Frage
Wenn sich Höhen wiederholen könnten und bis zu 10^9 reichen, welcher deiner Ansätze würde weiterhin unverändert funktionieren, und worüber würdest du eine binäre Suche durchführen?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Angenommen, du kennst den Wasserstand
t. Kannst du sagen, ob es einen Weg hindurch gibt? Wie ändert sich die Antwort, wenntsteigt?Eine Route benötigt so viel Zeit, bis das Wasser jede Zelle auf ihr bedeckt hat; die benötigte Zeit entspricht also der höchsten Zelle auf der Route. Gesucht ist die Route zwischen den Ecken, deren höchste Zelle so niedrig wie möglich ist.
Führe entweder eine binäre Suche über
tmit einer Flutfüllung als Test durch oder führe den Dijkstra-Algorithmus mit einem Min-Heap aus, bei dem die Zeit einer Zelle dem größeren Wert aus deiner Ankunftszeit und ihrer eigenen Höhe entspricht. Beende den Vorgang, wenn die Zelle unten rechts den Heap verlässt.
Lösung
Eine Route benötigt so viel Zeit wie ihre höchste Zelle, denn das Wasser muss jede Zelle bedecken, die du durchquerst. Finde also die Route zwischen den Ecken, deren höchste Zelle am niedrigsten ist: einen kürzesten Pfad, dessen Kosten das Maximum und nicht die Summe sind. Erhöhe den Wasserstand schrittweise, führe eine binäre Suche nach dem Wasserstand durch oder wende Dijkstras Algorithmus auf diese Kosten an.
Hebe das Wasser Schritt für Schritt an
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Lege einen Wasserstand t fest. Eine Flutung vom linken oberen Rand aus durch Zellen mit einer Höhe von höchstens t zeigt dir, ob die rechte untere Ecke erreichbar ist. Setze t zunächst auf die höhere der beiden Eckhöhen, max(grid[0][0], grid[n-1][n-1]), da beide Ecken unter Wasser liegen müssen, und erhöhe den Wert um 1, bis die Flutung durchkommt. Steigendes Wasser gibt nur weitere Zellen frei, daher ist der erste funktionierende Wasserstand die Antwort.
Jede Flutung kostet O(n²), und der Wasserstand kann fast n²-mal steigen: Bei einem Gitter mit 100 × 100 Zellen sind es bis zu 10^4 Wasserstände × 10^4 Zellen, also etwa 10^8 Zellbesuche.
Algorithmus
- Setze
tauf die größere der beiden Eckhöhen. - Führe eine Flutungssuche von oben links durch die Zellen mit einer Höhe von höchstens
taus, mit einem expliziten Stack und einer Markierung für besuchte Zellen. - Wenn die Suche unten rechts erreicht, gib
tzurück. - Andernfalls addiere 1 zu
tund führe die Suche erneut aus.
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 tBinäre Suche nach dem Wasserstand
Idee
Der Flood-Fill-Test schlägt für jede Stufe unterhalb der Antwort fehl und ist für jede Stufe ab der Antwort erfolgreich. Die binäre Suche findet diesen Umschlagpunkt zwischen der höheren Ecke und n²-1, wo das gesamte Raster unter Wasser steht.
Im Beispiel mit 5 × 5 gilt lo = 6 und hi = 24. Stufe 15 schlägt fehl, also gilt lo = 16. Die Stufen 20, 18, 17 und 16 sind alle erfolgreich, und nach fünf Füllvorgängen endet die Suche bei 16.
Ein Raster mit 100 × 100 hat 10^4 Stufen, daher entscheiden etwa 14 Füllvorgänge darüber: ungefähr 1.4 × 10^5 Zellbesuche statt 10^8.
Algorithmus
- Setze
loauf die Höhe der höheren Ecke undhiaufn²-1. - Solange
lo < higilt, berechnemid = (lo + hi) / 2und runde ab. - Führe einen Flood Fill auf der Ebene
middurch. Wenn er unten rechts ankommt, setzehi = mid; andernfalls setzelo = mid + 1. - Gib
lozurück.
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 auf der höchsten Zelle der Route
Idee
Weise jeder Route Kosten zu: den Wert ihres höchsten Feldes. Dijkstras Algorithmus funktioniert weiterhin, denn das Erweitern einer Route auf ein Feld mit der Höhe h kostet max(old cost, h) und ist niemals günstiger als die bisherigen Kosten. Halte einen Min-Heap mit den Feldern, sortiert nach dieser Zeit, und beginne oben links bei grid[0][0]. Wenn unten rechts den Heap verlässt, ist dessen Zeit die Antwort.
Du kannst ein Feld bereits beim ersten Einfügen als besucht markieren. Die Felder verlassen den Heap in der Reihenfolge ihrer Zeiten. Daher erreicht das erste Feld, das einen Nachbarn erreicht, diesen mit der kleinstmöglichen Zeit, und jedes Feld kommt nur einmal in den Heap.
Der Heap enthält den Rand des Bereichs, den du erreichen kannst, und bei jedem Entfernen steigt das Wasser gerade so weit, dass du dorthin gehen kannst. Im Beispiel mit 5 × 5 Feldern erfolgen die Entnahmen mit den Werten 0, 1, 2, 3, 4, 5, dann kommt das Tor bei 16 an die Reihe, und unten rechts verlässt den Heap mit 16.
Algorithmus
- Markiere die Zelle oben links als besucht und füge sie mit der Zeit
grid[0][0]hinzu. - Entnimm die Zelle mit der kleinsten Zeit
t. Wenn es die Zelle unten rechts ist, gibtzurück. - Markiere jeden noch nicht besuchten Nachbarn als besucht und füge ihn mit der Zeit
max(t, its height)hinzu. - Wiederhole den Vorgang ab Schritt 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))
Stolperfallen und Grenzfälle
- Die eigene Höhe einer Ecke ignorieren. Die Antwort beträgt mindestens
grid[0][0]undgrid[n-1][n-1]: Bei[[3, 0], [1, 2]]ist sie 3. - Gierig zum niedrigsten Nachbarn gehen. Die beste Route kann zu einem Durchgang hinaufführen und dann einen großen Umweg nehmen, wie im 5 × 5-Beispiel.
- Die Höhen entlang der Route addieren, wie bei einem gewöhnlichen kürzesten Weg. Die neue Zeit ist
max(t, height), nichtt + height. - Rekursion für die Flutfüllung verwenden. Eine gewundene Route kann Tausende Zellen lang sein, wodurch Pythons Grenze von 1.000 verschachtelten Aufrufen überschritten wird.
Häufige Fragen3
Wie hoch ist die Zeitkomplexität von Swim in Rising Water?
O(n² log n) mit Dijkstras Algorithmus: Jede der n² Zellen wird höchstens einmal in einen Heap eingefügt und daraus entnommen. Die binäre Suche nach dem Wasserstand hat dieselbe Komplexität, etwa log2(n²) Flood-Fills mit jeweils O(n²). Beide benötigen O(n²) Speicher.
Kann „Can Swim in Rising Water“ mit binärer Suche gelöst werden?
Ja. Ob du bei Stufe t hinüberkommst, wechselt an der Antwort einmal von falsch zu wahr. Eine binäre Suche über t mit einer Flutfüllung als Test benötigt etwa log2(n²) Flutfüllungen, bei einem 100 × 100-Raster sind das 14.
Kann Union-Find das Problem „Swim in Rising Water“ lösen?
Ja. Öffne die Zellen in der Reihenfolge ihrer Höhe, verbinde jede neue Zelle mit ihren offenen Nachbarn und höre auf, sobald die beiden Ecken zur selben Menge gehören. Die Höhe der zuletzt geöffneten Zelle ist die Antwort. Da jeder Wert von 0 bis n²-1 einmal vorkommt, gibt eine Tabelle von Höhe zu Zelle die Reihenfolge ohne Sortieren an.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def swimInWater(grid):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argument
grid = [[0, 2], [3, 1]]
Erwartete Ausgabe
2