Swim in Rising Water

Q: 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 mit bis zu n² Einträgen eingefügt und daraus entfernt. Die binäre Suche nach dem Wasserstand hat dieselbe Komplexität, etwa log2(n²) Flutfüllungen mit jeweils O(n²). Beide benötigen O(n²) Speicher für die Markierungen besuchter Zellen und den Heap oder Stapel.

Q: Warum funktioniert Dijkstras Algorithmus, wenn die Kosten dem Wert der höchsten Zelle entsprechen?

Dijkstra benötigt eine Eigenschaft: Das Verlängern einer Route verringert niemals ihre Kosten. Hier sind die neuen Kosten max(t, height) , die niemals unter t liegen, also ist die Eigenschaft erfüllt. Deshalb steht die Zeit einer Zelle beim ersten Entfernen aus dem Heap endgültig fest, und du kannst beim Ziel anhalten.

Q: Kann man „Can Swim in Rising Water“ mit binärer Suche lösen?

Ja. Ob du bei Level t hinübergelangen kannst, ist für jedes Level unterhalb der Antwort falsch und ab der Antwort wahr. Eine binäre Suche über t mit einer Flutfüllung als Test findet die Antwort in etwa log2(n²) Tests: 14 bei einem 100 × 100 großen Raster.

Q: Kann Union-Find das Problem „Swim in Rising Water“ lösen?

Ja. Öffne die Zellen der Höhe nach, verbinde jede neue Zelle mit ihren offenen Nachbarn und höre auf, sobald sich oben links und unten rechts in derselben Menge befinden. Die Höhe der zuletzt geöffneten Zelle ist die Antwort. Da das Raster jeden Wert von 0 bis n²-1 genau einmal enthält, liefert eine Tabelle, die Höhen Zellen zuordnet, die Öffnungsreihenfolge ohne Sortieren.

SchwerKürzeste Wege Heap Binäre Suche

+10

Du erhältst ein n × n-Raster aus Höhen, das jede Zahl von 0 bis n²-1 genau einmal enthält, als Liste von Zeilen. Der Regen beginnt zum Zeitpunkt 0, und 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 von einer Zelle in eine Zelle schwimmen, die eine Seite mit ihr teilt, wenn beide unter Wasser sind, und das Schwimmen dauert keine Zeit. Gib den frühesten Zeitpunkt zurück, zu dem du dich in der Zelle unten rechts befinden kannst.

Funktion

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

gridinteger-2d-array: die Höhen, als eine Liste von 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].length
1 ≤ n ≤ 100
0 ≤ grid[i][j] ≤ n²-1
Jeder Wert von 0 bis n²-1 kommt genau einmal vor.

Beispiele

Eingabe: grid = [[0, 2], [3, 1]]
Ausgabe: 2
Erklärung: Über die Zelle oben rechts verläuft der Weg 0, 2, 1, und seine höchste Zelle ist 2. Über die Zelle unten links verläuft er 0, 3, 1, mit der höchsten Zelle 3. Zum Zeitpunkt 2 steht der erste Weg unter Wasser, daher lautet die Antwort 2.

+13 versteckte Tests beim Einreichen

Weiterführende Frage

Wenn sich Höhen wiederholen könnten und bis zu 10^9 reichen würden: Welcher deiner Ansätze würde unverändert funktionieren, und wonach würdest du bei der binären Suche suchen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die benötigte Zeit für eine Route entspricht der höchsten Zelle, da das Wasser jede Zelle bedecken muss, durch die du gehst. Die Aufgabe besteht also darin, die Route zwischen den Ecken zu finden, deren höchste Zelle möglichst niedrig ist: ein kürzester Weg, bei dem die Kosten eines Weges seinem Maximum und nicht seiner Summe entsprechen. Du kannst das Wasser Schritt für Schritt ansteigen lassen und testen, mit demselben Test eine binäre Suche über den Wasserstand durchführen oder Dijkstras Algorithmus verwenden, wobei die höchste Zelle als Kostenwert gilt.

Hebe das Wasser Schritt für Schritt an

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Lege einen Wasserstand t fest. Die Zellen, die du erreichen kannst, sind diejenigen mit einer Höhe von höchstens t, die über solche Zellen mit dem Start verbunden sind. Eine Flutungssuche vom oberen linken Feld aus findet sie: Füge den Start hinzu, nimm eine Zelle heraus und füge jeden unbesuchten Nachbarn mit einer Höhe von höchstens t hinzu. Wird dabei das untere rechte Feld besucht, reicht der Wasserstand t aus.

Die Antwort ist der kleinste Wert t, bei dem die Flutungssuche durchkommt. Er kann nicht kleiner als die höhere der beiden Eckhöhen sein, max(grid[0][0], grid[n-1][n-1]), da beide Ecken unter Wasser liegen müssen. Beginne mit diesem Wert und erhöhe ihn um 1, bis die Suche erfolgreich ist. Der erste funktionierende Wasserstand ist die Antwort, denn steigendes Wasser öffnet nur Zellen und schließt keine: Ein Wasserstand, bei dem es funktioniert, funktioniert auch weiterhin.

Jeder Testfall kostet O(n²), und der Wasserstand kann fast n²-mal steigen, bevor die Suche durchkommt. Bei einem 100 × 100 großen Raster sind das bis zu 10^4 Wasserstände × 10^4 Zellen, also etwa 10^8 Zellbesuche. In den großen Tests enthalten die Ecken die Werte 0 und 1, und die Antworten liegen zwischen 4,950 und 9,998. Daher werden Tausende vollständige Flutungssuchen ausgeführt, bevor die Antwort gefunden wird.

Algorithmus

Setze t auf den höheren der beiden Eckwerte.
Führe eine Flutfüllung von oben links durch Zellen mit einer Höhe von höchstens t aus, mit einem expliziten Stack und einer Markierung für besuchte Zellen.
Wenn die Flutfüllung unten rechts erreicht, gib t zurück.
Andernfalls erhöhe t um 1 und führe die Flutfüllung 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 t

Binäre Suche nach dem Wasserstand

Idee

Der Test aus dem ersten Ansatz hat eine nützliche Form. Er schlägt für jede Stufe unterhalb der Antwort fehl und ist ab der Antwort für jede Stufe erfolgreich. Eine Ja-oder-Nein-Frage, deren Antwort genau einmal von Nein zu Ja wechselt, lässt sich mit binärer Suche in logarithmisch vielen Versuchen beantworten.

Suche zwischen lo, der höheren Ecke, und hi = n²-1, der höchsten Zelle, bei der das gesamte Gitter unter Wasser liegt und der Test erfolgreich sein muss. Teste die mittlere Stufe. Wenn du durchkommst, ist die Antwort höchstens mid, also setze hi = mid; andernfalls liegt sie über mid, also setze lo = mid + 1. Wenn sich beide treffen, ist diese Stufe die Antwort.

Im 5 × 5-Beispiel gilt lo = 6 und hi = 24. Stufe 15 schlägt fehl, weil der obere Bereich eingeschlossen ist, also setze lo = 16. Die Stufen 20, 18, 17 und 16 sind alle erfolgreich, wodurch hi auf 16 sinkt, und die Suche endet nach fünf Flutungsdurchläufen bei 16.

Ein 100 × 100-Gitter hat 10^4 Stufen, sodass etwa 14 Tests genügen, um die Antwort zu bestimmen, jeder mit O(n²): insgesamt rund 1.4 × 10^5 Zellenbesuche statt 10^8. Verwende eine iterative Flutung. Ein großer Testfall ist ein gewundener Korridor mit etwa 5,000 Zellen Länge, der viel tiefer ist als Pythons Grenze von 1,000 verschachtelten Aufrufen.

Algorithmus

Setze lo auf die Höhe der höheren Ecke und hi auf n²-1.
Solange lo < hi gilt, nimm mid = (lo + hi) / 2, abgerundet.
Führe eine Flutfüllung auf der Ebene mid durch. Wenn sie die untere rechte Ecke erreicht, setze hi = mid; andernfalls setze lo = mid + 1.
Gib lo zurü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 lo

Dijkstra auf der höchsten Zelle der Route

Idee

Betrachte das Raster als Graphen und weise jeder Route Kosten zu: die höchste Zelle, nicht die Summe ihrer Schritte. Dijkstras Algorithmus funktioniert mit diesen Kosten weiterhin, denn das Verlängern einer Route macht sie nie günstiger. Die Kosten der längeren Route sind max(old cost, new height), also niemals kleiner als die bisherigen Kosten. Genau diese eine Eigenschaft benötigt Dijkstra.

Verwende einen Min-Heap mit Zellen, deren Schlüssel ihre Zeit ist – die höchste Zelle auf der bisher besten Route zu ihnen. Beginne oben links mit der Zeit grid[0][0]. Entnimm die Zelle mit der kleinsten Zeit t; jeder Nachbar, den du noch nicht besucht hast, erhält die Zeit max(t, its height). Wenn unten rechts den Heap verlässt, ist ihre Zeit die Antwort.

Du kannst eine Zelle beim ersten Einfügen als besucht markieren. Zellen verlassen den Heap in der Reihenfolge ihrer Zeiten. Daher hat die erste Zelle, die einen Nachbarn erreicht, die kleinste Zeit aller Zellen, die ihn jemals erreichen werden, und die von ihr aus berechnete Zeit des Nachbarn ist optimal. Eine spätere Route kommt mit einer mindestens ebenso großen Zeit an. Jede Zelle wird also genau einmal mit ihrer endgültigen Zeit in den Heap eingefügt.

So steigt das Wasser Schritt für Schritt. Der Heap enthält den Rand des erreichbaren Gebiets, und wenn du die niedrigste Zelle entnimmst, steigt das Wasser genau so weit, dass du dorthin treten kannst. Im 5 × 5-Beispiel lauten die entnommenen Werte 0, 1, 2, 3, 4, 5 und dann das Tor bei 16. Danach erhält jede Zelle auf dem Umweg die Zeit 16, und unten rechts verlässt den Heap mit der Zeit 16, bevor irgendeine höhere Zelle entnommen wird.

Jede der n² Zellen wird höchstens einmal eingefügt und entnommen, jeweils in O(log n) Zeit. Die Laufzeit beträgt also O(n² log n), und die Suche endet, sobald das Ziel entnommen wird.

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, gib t zurück.
Markiere jeden noch nicht besuchten Nachbarn als besucht und füge ihn mit der Zeit max(t, its height) hinzu.
Wiederhole 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 meisten falschen Antworten entstehen, weil eine Ecke übersehen, ein Kostenwert addiert statt als Maximum berücksichtigt oder die Suche zu früh abgebrochen wird.

Die Höhe des Startfelds wird ignoriert. Du kannst dich nicht oben links befinden, bevor das Feld unter Wasser steht. Die Antwort ist also mindestens grid[0][0]. Bei [[3, 0], [1, 2]] ist die Antwort 3.
Die Höhe des Zielfelds wird ignoriert. Auch unten rechts muss das Feld unter Wasser stehen. Die Antwort ist also mindestens grid[n-1][n-1].
Du gehst gierig zum niedrigsten Nachbarfeld des aktuellen Felds. Die beste Route kann zu einem Durchgang hinaufführen und dann einen langen Umweg nehmen, wie im 5 × 5-Beispiel. Nur eine Suche entlang der gesamten Grenze des erreichten Bereichs findet sie.
Du addierst die Höhen entlang der Route wie bei einem gewöhnlichen kürzesten Weg. Die neue Zeit ist max(t, height), nicht t + height.
Du verwendest Rekursion für die Flutfüllung. Eine gewundene Route kann Tausende von Zellen lang sein, wodurch Python sein Limit von 1.000 verschachtelten Aufrufen überschreitet.
Du bewegst dich diagonal. Du kannst nur zu einem Feld schwimmen, das eine Seite mit deinem Feld teilt.

Häufige Fragen4

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 mit bis zu n² Einträgen eingefügt und daraus entfernt. Die binäre Suche nach dem Wasserstand hat dieselbe Komplexität, etwa log2(n²) Flutfüllungen mit jeweils O(n²). Beide benötigen O(n²) Speicher für die Markierungen besuchter Zellen und den Heap oder Stapel.

Warum funktioniert Dijkstras Algorithmus, wenn die Kosten dem Wert der höchsten Zelle entsprechen?

Dijkstra benötigt eine Eigenschaft: Das Verlängern einer Route verringert niemals ihre Kosten. Hier sind die neuen Kosten max(t, height), die niemals unter t liegen, also ist die Eigenschaft erfüllt. Deshalb steht die Zeit einer Zelle beim ersten Entfernen aus dem Heap endgültig fest, und du kannst beim Ziel anhalten.

Kann man „Can Swim in Rising Water“ mit binärer Suche lösen?

Ja. Ob du bei Level t hinübergelangen kannst, ist für jedes Level unterhalb der Antwort falsch und ab der Antwort wahr. Eine binäre Suche über t mit einer Flutfüllung als Test findet die Antwort in etwa log2(n²) Tests: 14 bei einem 100 × 100 großen Raster.

Kann Union-Find das Problem „Swim in Rising Water“ lösen?

Ja. Öffne die Zellen der Höhe nach, verbinde jede neue Zelle mit ihren offenen Nachbarn und höre auf, sobald sich oben links und unten rechts in derselben Menge befinden. Die Höhe der zuletzt geöffneten Zelle ist die Antwort. Da das Raster jeden Wert von 0 bis n²-1 genau einmal enthält, liefert eine Tabelle, die Höhen Zellen zuordnet, die Öffnungsreihenfolge ohne Sortieren.

Python

def swimInWater(grid):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet

Swim in Rising Water

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Hebe das Wasser Schritt für Schritt an

Binäre Suche nach dem Wasserstand

Dijkstra auf der höchsten Zelle der Route

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben