Ce este Flood Fill?

Umplerea de inundații este un algoritm utilizat în principal pentru a determina o zonă delimitată conectată la un nod dat într-o matrice multidimensională. Este o asemănare strânsă cu instrumentul cupă din programele de vopsire.

Cea mai abordată implementare a algoritmului este o funcție recursivă bazată pe stivă, și despre asta vom vorbi în continuare.

Cum functioneazã?

Problema este destul de simplă și de obicei urmează acești pași:

  1. Luați poziția punctului de plecare.
  2. Decideți dacă doriți să mergeți în 4 direcții ( N, S, W, E ) sau 8 direcții ( N, S, W, E, NW, NE, SW, SE ).
  3. Alegeți o culoare de înlocuire și o culoare țintă.
  4. Călătorește în acele direcții.
  5. Dacă țiglă pe care aterizați este o țintă, înlocuiți-o cu culoarea aleasă.
  6. Repetați 4 și 5 până când ați fost peste tot în interiorul granițelor.

Să luăm ca exemplu următoarea matrice:

imagine

Pătratul roșu este punctul de plecare, iar pătratele gri sunt așa-numiții pereți.

Pentru mai multe detalii, iată un cod care descrie funcția:

int wall = -1;

void flood_fill(int pos_x, int pos_y, int target_color, int color)
{
  
   if(a[pos_x][pos_y] == wall || a[pos_x][pos_y] == color) // if there is no wall or if i haven't been there
      return;                                              // already go back
   
   if(a[pos_x][pos_y] != target_color) // if it's not color go back
      return;
   
   a[pos_x][pos_y] = color; // mark the point so that I know if I passed through it. 
   
   flood_fill(pos_x + 1, pos_y, color);  // then i can either go south
   flood_fill(pos_x - 1, pos_y, color);  // or north
   flood_fill(pos_x, pos_y + 1, color);  // or east
   flood_fill(pos_x, pos_y - 1, color);  // or west
   
   return;

}

După cum s-a văzut mai sus, punctul meu de plecare este (4,4). După apelarea funcției pentru coordonatele de pornire x = 4 și y = 4 , Pot începe să verific dacă nu există perete sau culoare pe loc. Dacă acest lucru este valid, marchez locul cu unul “culoare” și începeți să verificați celelalte pătrate adiacente.

Mergând spre sud vom ajunge la punctul (5,4) și funcția rulează din nou.

Problema exercițiilor fizice

Întotdeauna am considerat că rezolvarea unei (sau mai multor) probleme folosind un algoritm nou învățat este cel mai bun mod de a înțelege pe deplin conceptul.

Iată deci unul:

Afirmație:

Într-o matrice bidimensională vi se dă n număr de “insule” . Încercați să găsiți cea mai mare zonă a unei insule și numărul de insulă corespunzător. 0 marchează apă și orice alt x între 1 și n marchează un pătrat de la suprafața corespunzătoare insulei x.

Intrare

  • n – numărul de insule.
  • l, c – dimensiunile matricei.
  • urmatorul l linii, c numere care dau l al treilea rând al matricei.

Ieșire

  • eu – numărul insulei cu cea mai mare suprafață.
  • A – zona eu insula a.

Ex:

Aveți următoarele informații:

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

Pentru care veți obține insula nr. 2 ca cea mai mare insulă cu o suprafață de 5 pătrate.

Sugestii

Problema este destul de ușoară, dar iată câteva sugestii:

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