Selgitatud üleujutuste täitmise algoritm

Üleujutuste täitmine on algoritm, mida kasutatakse peamiselt mitmemõõtmelise massiivi antud sõlmpunktiga ühendatud piiratud ala määramiseks. See on värviprogrammide lähedane sarnasus ämberriistaga.

Algoritmi kõige lähenemisviis on virnapõhine rekursiivne funktsioon ja sellest me räägime järgmisena.

Kuidas see töötab?

Probleem on üsna lihtne ja järgib tavaliselt neid samme:

  1. Võtke lähtepunkti asend.
  2. Otsustage, kas soovite minna 4 suunas ( N, S, W, E ) või 8 suunda ( N, S, W, E, NW, NE, SW, SE ).
  3. Valige asendusvärv ja sihtvärv.
  4. Reisige nendes suundades.
  5. Kui paan, millele maandute, on sihtmärk, asendage see valitud värviga.
  6. Korrake 4. ja 5., kuni olete olnud kõikjal piirides.

Võtame näiteks järgmise massiivi:

alt tekst

Punane ruut on lähtepunkt ja hallid väljakud on nn seinad.

Lisateabe saamiseks on siin kood, mis kirjeldab funktsiooni:

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

Nagu eespool näha, on minu lähtepunktiks (4,4). Pärast algkoordinaatide x = 4 ja y = 4 funktsiooni kutsumist saan hakata kontrollima, kas kohapeal pole seina ega värvi. Kui see on õige, tähistan koha ühe värviga ja hakkan teisi külgnevaid ruute kontrollima.

Lõuna poole liikudes jõuame punkti (5,4) ja funktsioon töötab uuesti.

Harjutusprobleem

Arvestasin alati, et (või mitme) probleemi (de) lahendamine vastõpitud algoritmi abil on parim viis mõistest täielikult aru saada.

Nii et siin on üks:

Avaldus:

Kahemõõtmelises massiivis antakse teile n arvu "saari" . Püüdke leida saare suurim pindala ja vastav saare number. 0 tähistab vett ja mis tahes muu x vahemikus 1 kuni n tähistab ühte ruutu saarele x vastava pinnaga.

Sisend

  • n - saarte arv.
  • l, c - maatriksi mõõtmed.
  • Järgmise l liinide c numbrid andes l th reas maatriksis.

Väljund

  • i - suurima pindalaga saare arv.
  • A - i saare piirkond.

Nt:

Teil on järgmine sisend:

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

Mille eest saate saare nr. 2 kui suurim saar, mille pindala on 5 ruutu.

Vihjed

Probleem on üsna lihtne, kuid siin on mõned näpunäited:

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