insule ( fill)

[•dornescuvlad]

Cod:

void fill(int x, int y)
{
	if (a[x][y-1]==1) fill(x,y-1);
	if (a[x][y+1]==1) fill(x,y+1);
	if (a[x-1][y]==1) fill(x-1,y);
	if (a[x+1][y]==1) fill(x+1,y);
	if (a[x-1][y-1]==1) fill(x-1,y-1);
	if (a[x-1][y+1]==1) fill(x-1,y+1);
	if (a[x+1][y-1]==1) fill(x+1,y-1);
	if (a[x+1][y+1]==1) fill(x+1,y+1);
}

ce nu e in regula cu functia asta?
imi da segmentation fault
cum aflu numarul de insule intr-o matrice cu val 0(apa),1,2,3 (cu ajutorul acestei functii) si de ce imi da segmentation fault?

[•Florian]

x si y pot deveni negative [ daca tot scazi din ele ] sau pot depasi limitele superioare ale matricei [ daca le tot aduni ]. Pune conditie ca x si y sa se afle in matrice [ x > 0 && y>0 && x<=N && y<=M ]. 

[•pauldb]

Nu e bine ca nu marchezi pozitiile prin care treci. Tu intri cu functia de mai sus o celula vecina de valoare 1 si apoi din acea celula te poti intoarce in celula initiala si tot asa. Programul face o bucla infinita, insa din cauza ca stiva e limitata (nu poti avea un numar infinit de apeluri de functii in ea), programul crapa si da Segmentation Fault.

[•alexandru92]

In loc sa pui 100 de if-uri, n-ar fi mai bine daca ai folosi un for?

Cod:

const int dx[]={ -1, 0, 1, 0 }; // deseanaza o celula in ea pui coordonatele x,y si apoi determeni vecini celulei prin   
const int dy[]={  0, 1, 0, -1 }; // incrementarea si/sau decrementarea lui x si y.
int uz[Nmax][Nmax]; // tin minte daca am fost in celula a[x][y], 0 - nevizitat, 1 -vizitat 
void fill( int x, int y )
{int xk, yk, i;
 //diversele operatii
       for( i=0; i < 4; ++i )
       {
           xk=x+dx[i]; yk=y+dy[i]; //determini noile coordonate
           if( xk < 0 || yk < 0 || xk >= N || yk <= M  || uz[xk][yk] ) // daca coordonatele sunt invalide, sau am mai fost pe aici
             continue; 
           uz[xk][yk]=1; //marchez ca vizitat;
          fill( xk, yk ); // ai grija, daca nu ai suficienta memorie poti face stack overflow
       }
}

Cel mai eficient ar fi sa folosesti un lee, cauti casutele  de acelasi tip ca si casuta de pornire.

[•dornescuvlad]

multumesc, sunt  prost recunosc

[•alexandru92]

prost recunosc

Nu, nu esti prost, doar ai nevoie de multe exercitii, ca noi toti de altfel