Flood Fill

[•Anamaria20]

  Unde pot gasi un articol bun despre Flood Fill, si eventual si o sursa in care este aplicat? De pe Wikipedia nu am inteles mare lucru si vreau sa invat algoritmul... Tot legat de el, sunt sanse sa se ceara la clasa a 9-a? Multumesc anticipat.

[•alexandru92]

Ma indoiesc ca va aparea ceva de genu la clasa a 9 dar nu strica sa sti.
In primul rand sti functii ( recursive ) ?

[•Anamaria20]

Da, pot sa zic ca ma descurc. Implica asa ceva?

[•alexandru92]

Da, pot sa zic ca ma descurc. Implica asa ceva?

Da.
 Hai sa analizam urmatoarea problema. Se da o matrice binara de n X m. Se cere sa se determine numarul de grupuri de 1.
Dintr-o casuta se poate deplasa pe toate cele 8 directii.
Ex:
input.txt
5 6
0 1 1 0 0 0
0 1 1 1 0 0
1 0 0 0 0 1
0 0 1 1 1 0
1 0 0 0 0 1
output.txt
3
Acum din casuta de coordonate ( x, y ) se poate ajunge in : ( x-1, y-1 ), ( x-1, y ), (x-1, y ), ( x, y-1 ), ( x, y+1 ), ( x+1, y-1) , ( x+1, y ), (x+1, y+1 ).

Cod:

#include <fstream>
#define Nmax 100

/*
 *
 */
using namespace std;
const int dx[]={ -1, -1, -1, 0, 0, 1, 1, 1 }, dy[]={ -1, 0, 1, -1, 1, -1, 0, 1 };
bool M[Nmax][Nmax]; //memorez matricea.
int N, M;
void fill( int x, int y )
{int xnou, ynou, i;
       for(  i=0; i < 8; ++i )
      {
              xnou=x+dx[i];
              ynou=y+dy[i];
              if( xnou < 0 || ynou < 0 || xnou >= N || ynou >= N || !M[xnou][ynou] ) /*daca coordonatele sunt invalide sau M[xnou][ynou] este 0 */
                continue;  //merg mai departe
              M[xnou][ynou]=0; //marche ca am fost pe aici 
              fill( xnou, ynou ); //si apelez functia pentru a vedea unde pot ajunge din noul patratel
      }
}
int main()
{
        int n, m, i, j, nr=0;
        ifstream in("input.txt");
        in>>n>>m;
        for( i=0; i < n; ++i )
            for( j=0; j < m; ++j )
                 in>>M[i][j];
        for( i=0; i < n; ++i )
            for( j=0; j < m; ++j )
                if( 1 == M[i][j] ) //am dat peste un grup
               {
                     ++nr; //numar
                      fill( i, j ); //si acum sa identific si restul elementelor din grup ca sa le marchez cu 0
                }
        ofstream out("output.txt");
        out<<nr;
        return 0;
}            

[•Anamaria20]

Multumesc mult. Am inteles care e ideea. Ma apuc de probleme cu el.

[•alexandru92]

Multumesc mult. Am inteles care e ideea. Ma apuc de probleme cu el.

Nu creda ca o sa poti rezolva prea multe probleme ( pe infoarena cel putin ) . Fill  fiind recursiv mananca multa memorie din stiva si consuma foarte mult timp pentru gestionarea stivei.
Eu iti recomand sa folosesti Algoritmul lui Lee. Algoritmul lui Lee foloseste o coada( un vector in care inserarea unui element se face la sfarsit si se extrage un elemente de la inceput ) pentru a stoca coordonatele.
Il poti folosi si pentru determinarea drumului minim dintre 2 puncte...

Cod:

#include <fstream>
#define Nmax 100

/*
 *
 */
using namespace std;
const int dx[]={ -1, -1, -1, 0, 0, 1, 1, 1 }, dy[]={ -1, 0, 1, -1, 1, -1, 0, 1 };
bool M[Nmax][Nmax]; //memorez matricea.
int N, M;
int C[Nmax*Nmax][2]; //daca stii liste simplu inlantuite ii si mai eficient :)
void lee( int x, int y )
{
       int p, u, i, xnou, ynou;
       C[0][0]=x;  C[0][1]=y;
       for( p=0, u=0;  p <= u; ++p )
      {
              x=C[p][0];
              y=C[p][1];
              for(   i=0; i < 8; ++i )
              {
                      xnou=x+dx[i];
                      ynou=y+dy[i];
                      if( xnou < 0 || ynou < 0 || xnou >= N || ynou >= N || !M[xnou][ynou] ) 
                           continue;
                     M[xnou][ynou]=0;
                     C[++u][0]=xnou; 
                     C[u][1]=ynou;
             }
       }
}
int main()
{
        int n, m, i, j, nr=0;
        ifstream in("input.txt");
        in>>n>>m;
        for( i=0; i < n; ++i )
            for( j=0; j < m; ++j )
                 in>>M[i][j];
        for( i=0; i < n; ++i )
            for( j=0; j < m; ++j )
                if( 1 == M[i][j] ) //am dat peste un grup
               {
                     ++nr; //numar
                      lee( i, j ); //si acum sa identific si restul elementelor din grup ca sa le marchez cu 0
                }
        ofstream out("output.txt");
        out<<nr;
        return 0;
}  

[•Anamaria20]

  Eu intrebam de Flood Fill pentru ca am gasit o problema in care trebuia aflat numarul de incaperi dintr-o cladire. De Lee stiam, dar chiar nu m-am gandit sa-l folosesc aici. Il foloseam numai in probleme cu drum minim dintre doua puncte. Acum cred ca m-am lamurit. 

[•chera_lary]

Practic daca transofrmi algoritmul de Fill din forma recursiva in forma iterativa se ajunge la forma algoritmului lui Lee.

[•SpiderMan]

Uite aceasta problema, e de clasa a 10-a, dar poti face doar punctul A), numarul de insule se afla cu algoritmul Flood Fill. A doua parte o faci cu algoritmul lui Lee. Pentru algoritmul lui Lee ai aici o problema.

[•alexandru92]

Uite aceasta problema, e de clasa a 10-a, dar poti face doar punctul A), numarul de insule se afla cu algoritmul Flood Fill. A doua parte o faci cu algoritmul lui Lee. Pentru algoritmul lui Lee ai aici o problema.

Ambele se fac cu lee

[•SpiderMan]

Bine, istetule, FLOOD FILL este totuna cu algoritmul lui Lee. Deci ori zic Flood-Fill, ori zic Lee, e totuna.

[•alexandru92]

Bine, istetule, FLOOD FILL este totuna cu algoritmul lui Lee. Deci ori zic Flood-Fill, ori zic Lee, e totuna.

Ambele fac aceeasi chestie, una e recursiv, alta e iterativ

[•pauldb]

Usor, nu deveniti temperamentali.

Dupa parerea mea, cel mai bine este sa stapaniti algoritmul BFS, restul sunt aplicatii in cazuri particulare.

[•blasterz]

Bine, istetule, FLOOD FILL este totuna cu algoritmul lui Lee. Deci ori zic Flood-Fill, ori zic Lee, e totuna.

Ambele fac aceeasi chestie, una e recursiv, alta e iterativ

Flood Fill nu este Lee!
Lee e defapt BFS si acesta determină drumuri cu nr minim de muchii.
Flood Fill poate fi implementat atât cu BFS cât si cu DFS.
DFS nu determină drumuri cu nr minim de muchi! ! !

[•alexandru92]

Nici n-am zis ca sunt aceeasi chestie, am zis ca fac acelasi lucru

[•blasterz]

Nici n-am zis ca sunt aceeasi chestie, am zis ca fac acelasi lucru

Ziceam mai mult pentru Robert..