Objašnjen algoritam za poplavu

Poplava je algoritam koji se uglavnom koristi za određivanje ograničenog područja povezanog s danim čvorom u višedimenzionalnom nizu. To je bliska sličnost s alatom sef u programima za bojanje.

Najpribliženija implementacija algoritma je rekurzivna funkcija temeljena na stogu, i o tome ćemo razgovarati sljedeće.

Kako radi?

Problem je prilično jednostavan i obično slijedi ove korake:

  1. Zauzmite položaj početne točke.
  2. Odlučite se želite li ići u 4 smjera ( N, S, W, E ) ili 8 smjerova ( N, S, W, E, NW, NE, SW, SE ).
  3. Odaberite zamjensku boju i ciljnu boju.
  4. Putujte u tim smjerovima.
  5. Ako je pločica na koju sletite meta, ponovo je postavite u odabranu boju.
  6. Ponavljajte 4 i 5 dok ne budete posvuda unutar granica.

Uzmimo sljedeći niz kao primjer:

alt tekst

Crveni kvadrat je početna točka, a sivi kvadratići su takozvani zidovi.

Za daljnje detalje, evo dijela koda koji opisuje funkciju:

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

Kao što se vidi gore, moje polazište je (4,4). Nakon poziva funkcije za startne koordinate x = 4 i y = 4 , mogu započeti provjeru nema li na licu mjesta zida ili boje. Ako je to valjano, mjesto označim jednom "bojom" i započnem provjeravati ostale adijacentne kvadrate.

Idući prema jugu doći ćemo do točke (5,4) i funkcija se ponovno pokreće.

Problem vježbanja

Uvijek sam smatrao da je rješavanje (ili više) problema pomoću novonaučenog algoritma najbolji način za potpuno razumijevanje koncepta.

Pa evo jednog:

Izjava:

U dvodimenzionalnom polju dajete n broj "otoka" . Pokušajte pronaći najveće područje otoka i odgovarajući broj otoka. 0 označava vodu i bilo koji drugi x između 1 i n označava jedan kvadrat od površine koja odgovara otoku x.

Ulazni

  • n - broj otoka.
  • l, c - dimenzije matrice.
  • sljedećih l redaka, c brojeva koji daju l- ti red matrice.

Izlaz

  • i - broj otoka s najvećom površinom.
  • A - područje i -og otoka.

Primjer:

Imate sljedeći ulaz:

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

Za koji ćete dobiti otok br. 2 kao najveći otok s površinom od 5 kvadrata.

Savjeti

Problem je prilično jednostavan, ali evo nekoliko savjeta:

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