Imprimă pagina - insule ( fill)

Titlul: insule ( fill)
Scris de: Vlad Eugen Dornescu din Noiembrie 18, 2009, 18:04:47

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?

Titlul: RÄƒspuns: insule ( fill)
Scris de: Florian Marcu din Noiembrie 18, 2009, 18:11:43

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

Titlul: Răspuns: insule ( fill)
Scris de: Paul-Dan Baltescu din Noiembrie 18, 2009, 18:20:36

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.

Titlul: RÄƒspuns: insule ( fill)
Scris de: alexandru din Noiembrie 18, 2009, 19:55:59

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.

Titlul: RÄƒspuns: insule ( fill)
Scris de: Vlad Eugen Dornescu din Noiembrie 19, 2009, 17:00:56

multumesc, sunt ](*,) prost recunosc :aha:

Titlul: RÄƒspuns: insule ( fill)
Scris de: alexandru din Noiembrie 19, 2009, 20:08:27

Citat din mesajul lui: Dornescu Vlad-Eugen din Noiembrie 19, 2009, 17:00:56

prost recunosc

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

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Vlad Eugen Dornescu din Noiembrie 18, 2009, 18:04:47