Rotting Oranges

+10

Du erhältst ein Raster als Liste gleich langer Zeilen. Jede Zelle ist 0 (leer), 1 (eine frische Orange) oder 2 (eine faule Orange). Jede Minute wird jede frische Orange, die eine Seite mit einer faulen Orange teilt – oben, unten, links oder rechts –, faul. Gib die Anzahl der Minuten zurück, bis keine frische Orange mehr übrig ist, oder -1, falls manche frische Orange niemals faulen kann. Bei einem Raster ohne frische Orangen zu Beginn werden 0 Minuten benötigt.

Funktion

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

gridinteger-2d-array: das Raster, eine Liste mit 0, 1 und 2 pro Zeile
Gibt zurückinteger: die Minuten, bis keine Orange mehr frisch ist, oder -1, wenn das nie passiert

Einschränkungen

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
Jede Zeile hat dieselbe Länge.
Jedes grid[i][j] ist 0, 1 oder 2.

Beispiele

Eingabe: grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]
Ausgabe: 6
Erklärung: Wenn man Zellen als (Zeile, Spalte) angibt, verlässt die Fäulnis (0,0) und folgt dem einzigen Weg: (0,1) in Minute 1, (0,2) und (1,1) in Minute 2, (2,1) in Minute 3, (2,0) und (2,2) in Minute 4, (2,3) in Minute 5. Die Orange bei (1,3) berührt nur (2,3), daher verdirbt sie als letzte in Minute 6.

+21 versteckte Tests beim Einreichen

Weiterführende Frage

Angenommen, jede frische Orange benötigt eine eigene Anzahl von Minuten, um zu verderben, sobald eine benachbarte Orange verdorben ist. Wie würdest du dann die Zeit bis zum Abschluss ermitteln?

Lösung

Der Fäulnisprozess beginnt gleichzeitig bei jeder faulen Orange und breitet sich mit einer Zelle pro Minute aus. Die Antwort ist also eine Entfernung: Wie viele Schritte die am weitesten entfernte frische Orange von der nächstgelegenen faulen Orange entfernt ist. Eine Breitensuche misst genau das, wenn du alle faulen Orangen in die Warteschlange legst, bevor du beginnst, und die Warteschlange Ebene für Ebene, Minute für Minute, abarbeitest.

Minute für Minute simulieren

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

Idee

Halte dich an die Beschreibung. Scanne in jeder Minute das gesamte Raster und liste jede frische Orange auf, die an eine faule grenzt. Lass sie dann alle faulen, erhöhe die Uhr um eins und scanne erneut. Beende den Vorgang, wenn ein Scan keine Orange zum Faulen findet. Ist zu diesem Zeitpunkt noch eine frische Orange im Raster, kann die Fäulnis sie niemals erreichen: Gib -1 zurück.

Erst auflisten, dann faulen lassen. Wenn du während eines Scans eine Orange faulen lässt, sieht eine Zelle, die später im selben Scan an die Reihe kommt, sie als faul und fault ebenfalls. Dadurch breitet sich die Fäulnis in einer Minute über mehrere Zellen aus und die Uhr zeigt einen zu niedrigen Wert an.

Das ist korrekt, aber jede Minute erfordert einen vollständigen Scan von Zeilen × Spalten Zellen, und die Anzahl der Minuten kann sich der Anzahl der Zellen annähern. In einem Raster mit 150 × 150 Zellen, in dem die frischen Orangen einen einzigen gewundenen Pfad bilden und die Fäulnis an dessen Anfang sitzt, braucht die Fäulnis 11,324 Minuten: 11,324 Scans mit jeweils 22,500 Zellen, also etwa 2.5 × 10^8 Zellenprüfungen, von denen fast alle Zellen betreffen, die sich nicht ändern können.

Algorithmus

Setze die Minuten auf 0.
Durchsuche das Raster und liste jede frische Orange auf, die einen faulen Nachbarn hat.
Wenn die Liste leer ist, halte an. Andernfalls verfaule jede aufgelistete Orange, erhöhe die Minuten um 1 und durchsuche das Raster erneut.
Gib -1 zurück, wenn eine frische Orange übrig ist, andernfalls die Minuten.

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

Mehrquellen-BFS nach Ebenen

Idee

Die Suche vergeudet Zeit mit Zellen, die weit vom Geschehen entfernt sind. Die einzigen Orangen, die zur Minute t+1 verderben können, sind frische Nachbarn der Orangen, die zur Minute t verdorben sind. Nimm also genau diese in eine Warteschlange auf: die Grenze der Fäulnis.

Beginne die Warteschlange mit allen Orangen, die zur Minute 0 verdorben sind, alle zusammen. Das ist der Teil mit mehreren Startpunkten. Eine frische Orange verdirbt in der Minute, die ihrer Entfernung zur nächstgelegenen verdorbenen Orange entspricht, und eine Breitensuche, die mit allen Startpunkten beginnt, erreicht jede Zelle zuerst von dem Startpunkt aus, der am nächsten liegt. Eine Suche erledigt die Arbeit einer Suche pro Startpunkt plus die Ermittlung des Minimums.

Arbeite dann in Ebenen. Zu Beginn einer Minute enthält die Warteschlange k Orangen, nämlich die, die in der letzten Minute verdorben sind. Nimm genau k vom Anfang; für jede lässt du ihre frischen Nachbarn verderben und fügst sie hinten hinzu. Wenn alle k abgearbeitet sind, ist eine Minute vergangen und die Warteschlange enthält die nächste Grenze. Im ersten Beispiel lauten die Ebenen {(0,0)}, {(0,1)}, {(0,2), (1,1)}, {(2,1)}, {(2,0), (2,2)}, {(2,3)}, {(1,3)}: sechs Schritte nach dem Start, also sechs Minuten.

Zähle die frischen Orangen einmal zu Beginn und verringere die Anzahl jedes Mal, wenn eine Orange verdirbt. Beende die Suche, sobald sie 0 erreicht, sonst würde die letzte Ebene eine Minute hinzufügen, in der nichts verdirbt, und gib -1 zurück, wenn die Warteschlange leer wird, während die Anzahl über 0 liegt. Jede Zelle kommt höchstens einmal in die Warteschlange und prüft vier Nachbarn, also beträgt der Aufwand O(rows × cols).

Algorithmus

Lege jede faule Orange in eine Warteschlange und zähle die frischen Orangen.
Setze die Minuten auf 0. Solange die Warteschlange nicht leer ist und noch frische Orangen vorhanden sind, erhöhe die Minuten um 1 und notiere die Größe k der Warteschlange.
Nimm k Orangen von vorne. Markiere jeden frischen Nachbarn innerhalb des Gitters als faul, verringere die Anzahl der frischen Orangen und füge ihn hinten hinzu.
Wenn die Schleife endet, gib die Minuten zurück, falls die Anzahl der frischen Orangen 0 beträgt, andernfalls -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

Stolperfallen und Grenzfälle

Die meisten falschen Antworten liegen hier um eine Minute daneben oder entstehen dadurch, dass die Suche an der falschen Stelle beginnt.

Eine Minute für die letzte Ebene mitzählen. Wenn die Schleife läuft, bis die Warteschlange leer ist, lässt ihr letzter Durchlauf nichts verfaulen und zählt trotzdem 1 hinzu. Beende die Schleife, sobald keine frische Orange mehr übrig ist.
Die Suche nacheinander bei jeder verfaulten Orange beginnen. Die erste Suche beansprucht jede Orange, die sie erreicht, mit ihrer eigenen Zeit, sodass zwei Quellen, die sich in der Mitte treffen sollten, eine zu hohe Zeit ergeben: [[2, 1, 1, 1, 1, 1, 1, 2]] braucht 3 Minuten, nicht 6.
Orangen während des Durchlaufs in der Version mit minutengenauer Auswertung verfaulen lassen. Eine Zelle, die später im selben Durchlauf untersucht wird, sieht sie dann als verfault an, und die Fäulnis breitet sich innerhalb einer Minute über mehrere Zellen aus.
-1 zurückgeben, weil es keine verfaulte Orange gibt. Wenn es auch keine frische Orange gibt, muss nichts geschehen: [[0]] gibt 0 zurück. Nur frische Orangen, die nie verfaulen, führen zur Antwort -1.
Eine Orange erst dann als verfault markieren, wenn du sie aus der Warteschlange nimmst, statt wenn du sie hineinlegst. Eine Orange neben zwei verfaulten Orangen wird dann zweimal hinzugefügt und die Anzahl frischer Orangen sinkt unter null.
Tiefensuche verwenden. Sie folgt einem Pfad so weit wie möglich, daher sagt der Zeitpunkt, zu dem sie eine Orange zum ersten Mal erreicht, nichts darüber aus, in welcher Minute diese Orange verfault.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Rotting Oranges?

O(rows × cols) mit Breitensuche. Beim ersten Durchlauf wird jede Zelle einmal betrachtet, und jede orangefarbene Orange kommt höchstens einmal in die Warteschlange und überprüft vier Nachbarzellen. Die Warteschlange benötigt im schlimmsten Fall O(rows × cols) Speicherplatz, wenn das Gitter voller fauler Orangen ist.

Warum BFS und nicht DFS für „Rotting Oranges“ verwenden?

Die Breitensuche besucht Zellen in der Reihenfolge ihrer Entfernung vom Startpunkt, und die Entfernung entspricht hier der Zeit: Ebene k der Suche ist genau die Menge der Orangen, die in Minute k verderben. Die Tiefensuche kann eine Zelle über einen langen Umweg erreichen, bevor sie den kurzen Weg findet. Deshalb müsste sie Zellen jedes Mal erneut besuchen, wenn sie einen kürzeren Weg findet.

Was ist BFS mit mehreren Quellen?

Eine Breitensuche, die mit mehreren Zellen in der Warteschlange bei Abstand 0 statt mit einer startet. In einem einzigen Durchlauf liefert sie für jede Zelle ihren Abstand zur nächsten Quelle – dasselbe Ergebnis wie eine Suche pro Quelle mit anschließendem Ermitteln des Minimums, aber mit den Kosten nur einer Suche. Jede Frage nach dem „Abstand zum nächsten X“ in einem Raster lässt sich damit lösen.

Kannst du „Rotting Oranges“ lösen, ohne das Raster zu verändern?

Ja. Verwende ein separates Besuchsarray und prüfe dieses, anstatt eine 2 in das Raster zu schreiben. Das kostet zusätzlichen Speicherplatz von O(rows × cols), den die Warteschlange ohnehin benötigen kann. In Sprachen, die das Raster als Referenz übergeben, verändert das Hineinschreiben außerdem das Raster des Aufrufers, worauf dich ein Interviewer möglicherweise anspricht.

Python

def orangesRotting(grid):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet