Hochwasserfüllalgorithmus erklärt

Flood Fill ist ein Algorithmus, der hauptsächlich verwendet wird, um einen begrenzten Bereich zu bestimmen, der mit einem bestimmten Knoten in einem mehrdimensionalen Array verbunden ist. Es ist eine große Ähnlichkeit mit dem Schaufelwerkzeug in Malprogrammen.

Die am weitesten verbreitete Implementierung des Algorithmus ist eine stapelbasierte rekursive Funktion, und darüber werden wir als nächstes sprechen.

Wie funktioniert es?

Das Problem ist ziemlich einfach und folgt normalerweise den folgenden Schritten:

  1. Nehmen Sie die Position des Startpunktes ein.
  2. Entscheiden Sie, ob Sie in 4 Richtungen ( N, S, W, E ) oder 8 Richtungen ( N, S, W, E, NW, NE, SW, SE ) fahren möchten .
  3. Wählen Sie eine Ersatzfarbe und eine Zielfarbe.
  4. Reisen Sie in diese Richtungen.
  5. Wenn das Plättchen, auf dem Sie landen, ein Ziel ist, setzen Sie es erneut mit der gewählten Farbe ein.
  6. Wiederholen Sie 4 und 5, bis Sie überall innerhalb der Grenzen waren.

Nehmen wir als Beispiel das folgende Array:

Alt-Text

Das rote Quadrat ist der Ausgangspunkt und die grauen Quadrate sind die sogenannten Wände.

Für weitere Details finden Sie hier einen Code, der die Funktion beschreibt:

int wall = -1; void flood_fill(int pos_x, int pos_y, int target_color, int color) 

Wie oben gesehen, ist mein Ausgangspunkt (4,4). Nachdem ich die Funktion für die Startkoordinaten x = 4 und y = 4 aufgerufen habe, kann ich prüfen, ob an der Stelle keine Wand oder Farbe vorhanden ist. Wenn das gültig ist, markiere ich den Punkt mit einer „Farbe“ und beginne, die anderen benachbarten Quadrate zu überprüfen.

Wenn wir nach Süden gehen, kommen wir zu Punkt (5,4) und die Funktion wird erneut ausgeführt.

Übungsproblem

Ich habe immer gedacht, dass das Lösen eines (oder mehrerer) Probleme mit einem neu erlernten Algorithmus der beste Weg ist, um das Konzept vollständig zu verstehen.

Also hier ist eine:

Erklärung:

In einem zweidimensionalen Array erhalten Sie n Anzahlen von „Inseln“ . Versuchen Sie, die größte Fläche einer Insel und die entsprechende Inselnummer zu finden. 0 markiert Wasser und jedes andere x zwischen 1 und n markiert ein Quadrat von der Oberfläche, die der Insel x entspricht.

Eingang

  • n - die Anzahl der Inseln.
  • l, c - die Abmessungen der Matrix.
  • die nächsten l Zeilen, c Zahlen geben die l- te Zeile der Matrix an.

Ausgabe

  • i - die Nummer der Insel mit der größten Fläche.
  • A - das Gebiet der i -ten Insel.

Ex:

Sie haben folgende Eingabe:

2 4 4 0 0 0 1 0 0 1 1 0 0 0 2 2 2 2 2

Für die Sie Insel Nr. Erhalten. 2 als größte Insel mit einer Fläche von 5 Plätzen.

Hinweise

Das Problem ist recht einfach, aber hier sind einige Hinweise:

1. Use the flood-fill algorithm whenever you encounter a new island. 2. As opposed to the sample code, you should go through the area of the island and not on the ocean (0 tiles).