Afişează mesaje
):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.{
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);
}
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.{
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);
}
}
}
}
Intrebarea mea este: care dintre acesti algoritmi este mai eficient din punctul de vedere al memoriei folosite? Care dintre ei este mai rapid?
