Flood Fill Algorithm Explained

Flood fill er en algoritme, der hovedsagelig bruges til at bestemme et afgrænset område, der er forbundet med en given node i et flerdimensionelt array. Det er en tæt lighed med skovlværktøjet i maleprogrammer.

Den mest nærmede implementering af algoritmen er en stakbaseret rekursiv funktion, og det er det, vi taler om næste.

Hvordan virker det?

Problemet er ret simpelt og følger normalt disse trin:

  1. Tag positionen som startpunktet.
  2. Beslut, om du vil gå i 4 retninger ( N, S, W, E ) eller 8 retninger ( N, S, W, E, NW, NE, SW, SE ).
  3. Vælg en erstatningsfarve og en målfarve.
  4. Rejs i disse retninger.
  5. Hvis flisen du lander på er et mål, skal du genplacere den med den valgte farve.
  6. Gentag 4 og 5, indtil du har været overalt inden for grænserne.

Lad os tage følgende array som et eksempel:

alt tekst

Den røde firkant er udgangspunktet, og de grå firkanter er de såkaldte vægge.

For yderligere detaljer, her er et stykke kode, der beskriver funktionen:

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

Som set ovenfor er mit udgangspunkt (4,4). Efter at have kaldt funktionen til startkoordinaterne x = 4 og y = 4 , kan jeg begynde at kontrollere, om der ikke er nogen væg eller farve på stedet. Hvis det er gyldigt, markerer jeg stedet med en “farve” og begynder at kontrollere de andre adiacente firkanter.

Når vi går sydpå kommer vi til punkt (5,4), og funktionen kører igen.

Træningsproblem

Jeg har altid anset det for at løse en (eller flere) problem (er) ved hjælp af en nyindlært algoritme er den bedste måde at forstå konceptet fuldt ud på.

Så her er en:

Udmelding:

I et todimensionalt array får du et antal “øer” . Prøv at finde det største område på en ø og det tilsvarende ønummer. 0 markerer vand og ethvert andet x mellem 1 og n markerer et kvadrat fra overfladen svarende til ø x.

Indgang

  • n - antallet af øer.
  • l, c - matrixens dimensioner.
  • de næste l linjer, c tal, der giver matrixens 1. række.

Produktion

  • i - antallet af øen med det største område.
  • A - det område af i 'th ø.

Eks:

Du har følgende input:

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

For hvilken du får ø nr. 2 som den største ø med området på 5 firkanter.

Tips

Problemet er ret let, men her er nogle tip:

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).