Imprimă pagina - Eficienta Lee recursiv vs Lee liniar

Tocmai astazi am invatat cum se face algoritmul lui Lee folosind coada. Dar am dat de o problema (nush daca putem chiar asa :?):

Algoritmul recursiv mi s-a spus ca ar folosi mai multa memorie si nu ar fi tocmai eficient. Un exemplu de implementare in C++ arata ceva de genul:

Cod:

void lee(int x, int y, int k)
{
      mat[x][y]=k;
      if(k<mat[x+1][y]) lee(x+1, y, k+1);
      if(k<mat[x-1][y]) lee(x-1, y, k+1);
      if(k<mat[x][y+1]) lee(x, y+1, k+1);
      if(k<mat[x][y-1]) lee(x, y-1, k+1);
}

Acest algoritm functioneaza pe o matrice unde spatiile libere sunt egale cu n*m, iar spatiile inchise cu -1. Evident, matricea este bordata.

Al doilea algoritm (si cel pe care l-am vazut foarte mult pe internet) presupune folosirea unei cozi unde se afla vecinii elementului.

Cod:

void Fill(int x, int y)
{
    int a=harta[x][y];
    coord aux, urm;
    harta[x][y]=0;
    aux.x=x; aux.y=y;
    coada.push(aux); // de aici pornim
    while(!coada.empty()) // cat timp mai avem vecini
    {
        aux.x=coada.front().x; //cout<<coada.front().x<<' ';
        aux.y=coada.front().y; //cout<<coada.front().y<<"   ";
        coada.pop();
        for(int dir=0; dir<4; dir++)
        {
            urm.x=aux.x+dx[dir];
            urm.y=aux.y+dy[dir];
            if(ok(urm.x, urm.y) && harta[urm.x][urm.y]==a)
            {
                harta[urm.x][urm.y]=0;
                coada.push(urm);
            }
        }
    }
}

Teoretic este un algoritm de fill, dar cu cateva modificari poate deveni foarte usor Lee.

Intrebarea mea este: care dintre acesti algoritmi este mai eficient din punctul de vedere al memoriei folosite? Care dintre ei este mai rapid?

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Vlad Mihail din Februarie 27, 2019, 21:16:34