Flood Fill

Q: Wie hoch ist die Zeitkomplexität von Flood Fill?

O(m × n) für ein Bild mit m Zeilen und n Spalten. Jedes Pixel des Bereichs wird einmal auf den Stapel gelegt und betrachtet vier Nachbarn; Pixel außerhalb des Bereichs werden nur als Nachbarn betrachtet. Der Stapel kann bis zu m × n Pixel enthalten, wenn das gesamte Bild einen Bereich bildet.

Q: Solltest du für Flood Fill BFS oder DFS verwenden?

Beides funktioniert und benötigt jeweils O(m × n) Zeit. Der Bereich ist derselbe, unabhängig davon, in welcher Reihenfolge du ihn durchläufst. Daher färben eine Warteschlange (Breitensuche) und ein Stapel (Tiefensuche) dieselben Pixel. Wähle die Variante, die in deiner Sprache kürzer zu schreiben ist, und vermeide Rekursion bei großen Bildern.

Q: Warum läuft Flood Fill endlos, wenn die neue Farbe mit der alten übereinstimmt?

Die übliche Lösung behandelt „hat noch die alte Farbe“ als „noch nicht besucht“. Wenn die neue Farbe mit der alten Farbe übereinstimmt, ändert das Einfärben eines Pixels nichts. Daher legen seine Nachbarn ihn erneut auf den Stapel, und die Suche endet nie. Wenn du zuerst diesen Fall prüfst und das Bild zurückgibst, ist das Problem behoben; das unveränderte Bild ist die richtige Antwort.

Q: Kann Flood Fill rekursiv gelöst werden?

Ja, eine Funktion, die ein Pixel einfärbt und sich für jeden Nachbarn der alten Farbe selbst aufruft, ist korrekt. Das Risiko liegt in der Tiefe: Die Rekursion geht so tief wie der längste Pfad, dem die Suche folgt. In einer gewundenen Region können das Tausende von Aufrufen sein. Ein expliziter Stack erledigt dieselbe Arbeit ohne diese Begrenzung.

LeichtGraphen

+10

Ein Bild ist ein Raster aus ganzen Zahlen, wobei jede Zahl die Farbe eines Pixels angibt. Du erhältst das Bild als Liste von Zeilen, ein Startpixel in Zeile sr und Spalte sc sowie eine neue color. Färbe die zusammenhängende Region des Startpixels neu ein: jedes Pixel mit derselben Farbe wie das Startpixel, das du von dort aus erreichen kannst, indem du dich durch Pixel derselben Farbe nach oben, unten, links oder rechts bewegst. Gib das Bild nach dem Neufärben zurück.

Funktion

floodFill(image: integer-2d-array, sr: integer, sc: integer, color: integer) → integer-2d-array

imageinteger-2d-array: das Bild als Liste von Zeilen, eine Zahl pro Pixel
srinteger: die Zeile des Startpixels, gezählt ab 0
scinteger: die Spalte des Startpixels, gezählt ab 0
colorinteger: die neue Farbe für den Bereich
Gibt zurückinteger-2d-array: Das Bild, nachdem der Bereich neu gezeichnet wurde

Einschränkungen

1 ≤ image.length ≤ 80
1 ≤ image[i].length ≤ 80
Jede Zeile hat dieselbe Länge.
0 ≤ image[i][j], color ≤ 65535
0 ≤ sr < image.length und 0 ≤ sc < image[0].length

Beispiele

Eingabe: image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]sr = 0sc = 0color = 5
Ausgabe: [[5, 5, 0], [5, 0, 5], [5, 5, 5]]
Erklärung: Der Startpunkt hat die Farbe 1. Die 1 rechts davon, die 1en in der linken Spalte und in der unteren Zeile sowie die 1 über der unteren rechten Ecke sind alle damit verbunden, sodass alle sieben zu 5 werden. Die beiden 0en haben eine andere Farbe und behalten sie.

+18 versteckte Tests beim Einreichen

Weiterführende Frage

Wie würde sich deine Lösung ändern, wenn auch Pixel, die sich nur an einer Ecke berühren, als verbunden gelten würden?

Lösung

Die Region ist ein zusammenhängender Teil eines Graphen: Pixel sind Knoten, und zwei Pixel der Ausgangsfarbe, die eine Seite gemeinsam haben, sind verbunden. Jede Suche, die beim angegebenen Pixel beginnt und sich nur durch Pixel dieser Farbe bewegt, findet die gesamte Region. Die beiden Fallstricke sind ein Bild, bei dem die neue Farbe der alten entspricht, und eine lange, gewundene Region, an der eine rekursive Suche scheitert.

Tiefensuche mit Rekursion

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

Idee

Schreibe eine Funktion paint(r, c), die eine kleine Aufgabe erledigt: Wenn (r, c) innerhalb des Bildes liegt und noch die alte Farbe hat, gib ihm die neue Farbe und rufe die Funktion für die vier Nachbarpixel auf. Ein Aufruf für das Startpixel breitet sich über die gesamte Region aus, weil jedes Pixel der Region über einen Pfad aus Pixeln mit der alten Farbe mit dem Startpixel verbunden ist und die Aufrufe diesem Pfad folgen.

Das Pixel vor den vier Aufrufen anzumalen verhindert, dass sich die Ausbreitung im Kreis bewegt: Wenn ein Nachbar ein bereits angemaltes Pixel erneut aufruft, stimmt die Farbe nicht mehr überein und der Aufruf kehrt sofort zurück. Das funktioniert nur, wenn sich die neue Farbe von der alten unterscheidet. Prüfe das also zuerst und gib das Bild unverändert zurück, wenn beide Farben gleich sind.

Der Aufwand beträgt O(m × n), aber der Aufrufstapel ist die Schwachstelle. Die Rekursion geht so tief wie der Pfad, dem sie folgt. Eine ein Pixel breite Schlange durch ein Bild mit den Maßen 80 × 80 ist etwa 3.200 Pixel lang, sodass sich die Aufrufe ungefähr 3.200 Ebenen tief verschachteln. Python begrenzt die Rekursionstiefe standardmäßig auf 1.000 und löst dann einen Fehler aus. Deshalb funktioniert dieser Ansatz bei den größten Tests nicht. Andere Sprachen erlauben tiefere Aufrufe, aber bei einem größeren Bild wäre auch dort der Aufrufstapel irgendwann erschöpft.

Algorithmus

Lies old = image[sr][sc]. Wenn old gleich color ist, gib das Bild zurück.
Definiere paint(r, c): Kehre zurück, wenn (r, c) außerhalb des Bildes liegt oder seine Farbe nicht old ist.
Setze andernfalls image[r][c] = color und rufe paint für die Pixel oberhalb, unterhalb, links und rechts auf.
Rufe paint(sr, sc) auf und gib das Bild zurück.

def floodFill(image, sr, sc, color):
    old = image[sr][sc]
    if old == color:
        return image
    rows, cols = len(image), len(image[0])

    def paint(r, c):
        # Stop outside the image and at any pixel that is not the old color.
        if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != old:
            return
        image[r][c] = color
        paint(r + 1, c)
        paint(r - 1, c)
        paint(r, c + 1)
        paint(r, c - 1)

    paint(sr, sc)
    return image

Tiefensuche mit einem expliziten Stack

Idee

Führe denselben Durchlauf aus, aber speichere die noch zu besuchenden Pixel auf einem eigenen Stack statt auf dem Aufrufstack. Färbe das Startpixel und lege es auf den Stack. Nimm ein Pixel vom Stack, betrachte seine vier Nachbarn und färbe jeden Nachbarn innerhalb des Bildes, der noch die alte Farbe hat, und lege ihn auf den Stack. Wenn der Stack leer ist, hast du die gesamte Region gefärbt.

Färbe ein Pixel, wenn du es auf den Stack legst, nicht wenn du es herunter nimmst. Ein gefärbtes Pixel hat nicht mehr die alte Farbe, daher dient die Farbprüfung zugleich als Prüfung, ob das Pixel bereits besucht wurde: Kein Pixel gelangt zweimal auf den Stack, und du brauchst kein separates Markierungsraster. Wie bei der rekursiven Version muss sich die neue Farbe von der alten unterscheiden. Gib daher das Bild unverändert zurück, wenn beide gleich sind.

Jedes Pixel der Region wird einmal auf den Stack gelegt und prüft vier Nachbarn, daher beträgt die Laufzeit O(m × n). Der Stack enthält höchstens so viele Pixel wie die Region. Er liegt im normalen Speicher, daher ist eine gewundene Region mit 3.200 Pixeln kein Problem – bei der rekursiven Version lief der Aufrufstack über.

Algorithmus

Lies old = image[sr][sc]. Wenn old gleich color ist, gib das Bild zurück.
Färbe (sr, sc) ein und lege es auf einen Stapel.
Nimm ein Pixel vom Stapel und betrachte seine vier Nachbarn.
Färbe jeden Nachbarn innerhalb des Bildes, dessen Farbe old ist, ein und lege ihn auf den Stapel.
Wenn der Stapel leer ist, gib das Bild zurück.

def floodFill(image, sr, sc, color):
    old = image[sr][sc]
    # Painting a region its own color changes nothing. Returning here also
    # stops the search from pushing the same cells forever.
    if old == color:
        return image
    rows, cols = len(image), len(image[0])
    image[sr][sc] = color
    stack = [(sr, sc)]
    while stack:
        r, c = stack.pop()
        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 image[nr][nc] == old:
                # Paint on push: a painted cell no longer matches old,
                # so it can never be pushed twice.
                image[nr][nc] = color
                stack.append((nr, nc))
    return image

Stolperfallen und Grenzfälle

Die meisten falschen Antworten beruhen auf demselben Sonderfall mit der Farbe, darauf, dass das Bild verlassen wird, oder auf Rekursion in einem großen Bereich.

Den Fall vergessen, in dem color der Startfarbe entspricht. Das Übermalen ändert dann nichts, sodass eine Suche, die die Farbe als Markierung für besuchte Pixel verwendet, dieselben Pixel endlos zur Warteschlange hinzufügt.
image[sr][sc] auslesen, nachdem du es übermalt hast. Speichere zuerst die alte Farbe, sonst vergleichst du jeden Nachbarn mit der neuen Farbe.
Diagonale Nachbarn mitzählen. Pixel, die sich nur an einer Ecke berühren, sind nicht miteinander verbunden.
Die Farbe eines Nachbarn prüfen, bevor du geprüft hast, ob er sich innerhalb des Bildes befindet. Prüfe zuerst 0 ≤ row < rows und 0 ≤ col < cols.
Rekursion in einem großen Bild. Ein ein Pixel breiter Pfad durch ein Bild mit den Maßen 80 × 80 ist etwa 3.200 Pixel lang – tief genug, um Pythons Rekursionsgrenze zu überschreiten.
Jedes Pixel der alten Farbe im gesamten Bild übermalen. Pixel dieser Farbe, die vom Startpunkt abgeschnitten sind, müssen ihre Farbe behalten.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Flood Fill?

O(m × n) für ein Bild mit m Zeilen und n Spalten. Jedes Pixel des Bereichs wird einmal auf den Stapel gelegt und betrachtet vier Nachbarn; Pixel außerhalb des Bereichs werden nur als Nachbarn betrachtet. Der Stapel kann bis zu m × n Pixel enthalten, wenn das gesamte Bild einen Bereich bildet.

Solltest du für Flood Fill BFS oder DFS verwenden?

Beides funktioniert und benötigt jeweils O(m × n) Zeit. Der Bereich ist derselbe, unabhängig davon, in welcher Reihenfolge du ihn durchläufst. Daher färben eine Warteschlange (Breitensuche) und ein Stapel (Tiefensuche) dieselben Pixel. Wähle die Variante, die in deiner Sprache kürzer zu schreiben ist, und vermeide Rekursion bei großen Bildern.

Warum läuft Flood Fill endlos, wenn die neue Farbe mit der alten übereinstimmt?

Die übliche Lösung behandelt „hat noch die alte Farbe“ als „noch nicht besucht“. Wenn die neue Farbe mit der alten Farbe übereinstimmt, ändert das Einfärben eines Pixels nichts. Daher legen seine Nachbarn ihn erneut auf den Stapel, und die Suche endet nie. Wenn du zuerst diesen Fall prüfst und das Bild zurückgibst, ist das Problem behoben; das unveränderte Bild ist die richtige Antwort.

Kann Flood Fill rekursiv gelöst werden?

Ja, eine Funktion, die ein Pixel einfärbt und sich für jeden Nachbarn der alten Farbe selbst aufruft, ist korrekt. Das Risiko liegt in der Tiefe: Die Rekursion geht so tief wie der längste Pfad, dem die Suche folgt. In einer gewundenen Region können das Tausende von Aufrufen sein. Ein expliziter Stack erledigt dieselbe Arbeit ohne diese Begrenzung.

Python

def floodFill(image, sr, sc, color):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]
sr = 0
sc = 0
color = 5

Erwartet

[[5, 5, 0], [5, 0, 5], [5, 5, 5]]