Drumul printr-o matrice cu obstacole ne punctiforme

[•NXJoker]

Salut,
Am primit de la scoala o problema facultativa care se refera la cum putem parcurge o curte in care se afla obstacole..
in fisierul drum.in pe prima linie se afla un nr nat n care reprezinta nr de linii si coloane al matricei iar pe urmatoarele n linii cate n elemente: ' 0 ' daca se poate trece prin punctul respectiv si ' x ' daca nu se poatr trece.
se cere gasirea unui drum intre punctul m[0][0] si m[n][n] in care punctele prin care trecem sa fie marcate cu  ' D '.
Ma poate ajuta cineva ? pls..
mentionez ca sunt clasa a 10-ea si deci nu pot sa folosesc vre-o metoda prea sofisticata

[•Oancea.Catalin]

La aceasta problema se poate folosi algoritmul lui Lee . Depinde in cate directii te poti deplasa din punctul curent (4 sau 8 ). Daca gasesti solutie la aceasta problema poti rezolva si problema asta. Sunt foarte asemanatoare si destul de interesante.

Cod:

Consideram o tabla de sah de dimensiune NxN (n<=10). Sa se determine un drum de lungime minima prin care un cal aflat in pozitia (Xi, Yi) se deplaseaza in pozitia (Xf, Yf).
Exemplu
in.
5
1 2 // pozitia initiala
2 5//pozitia finala

out.
(1,2) (3,3) (2,5)

Problema se gaseste in culegerea de probleme "Fundamentele programarii" pentru clasa a XI-a scrisa de Mircea Pasoi si Dana Lica.

Daca nu stii inca nimic de algoritmul lui Lee poti sa imi dai un PM... te pot ajuta ... succes!

[•NXJoker]

am auzit de algoritmul lee dar nu am nici cea mai vaga idee despe ce e si cum functioneza .. 

[•Oancea.Catalin]

Cod:

int main()
{
	f>>n>>m; //n=dimensiuni matrice nxn ; m=obstacole
	for(i=1; i<=m; i++)
	{
		f>>x>>y; //coordonate obstacole
		a[x][y]=-1; //obstacolele le marchezi cu -1
	}
	f>>x_plecare>>y_plecare>>x_sosire>>y_sosire; // coordonare plecare si sosire
	
	a[x_plecare][y_plecare]=1; //punctul din care pleci il pui 1
	contor=0;
	contor++;
	coada_x[contor]=x_plecare; //tii o coada a x-ilor marcati
	coada_y[contor]=y_plecare; // si o coada a y-grecilor ... poti folosii structuri
	
	for(i=1; i<=contor; i++)//parcurgi coada
	{
		if(coada_x[i]==x_sosire && coada_y[i]==y_sosire) //daca a ajuns la final returneaza lungimea drumului minim
		{
			g<<a[x_sosire][y_sosire];
			return 0;
		}
		if(a[coada_x[i]][coada_y[i]+1]==0 && coada_y[i]+1<=n) //verifica daca poate sa marcheze vecinii
		{
			a[coada_x[i]][coada_y[i]+1]=a[coada_x[i]][coada_y[i]]+1; // vecinii sunt marcati cu valoarea punctului in care se afla +1
			contor++; // elementele cozii cresc
			coada_x[contor]=coada_x[i]; // coordonatele noilor vecini vizitati sunt puse in coada
			coada_y[contor]=coada_y[i]+1;
		}
		if(a[coada_x[i]][coada_y[i]-1]==0 && coada_y[i]-1>=1)
		{
			a[coada_x[i]][coada_y[i]-1]=a[coada_x[i]][coada_y[i]]+1;
			contor++;
			coada_x[contor]=coada_x[i];
			coada_y[contor]=coada_y[i]-1;
		}
		if(a[coada_x[i]+1][coada_y[i]]==0 && coada_x[i]+1<=n)
		{
			a[coada_x[i]+1][coada_y[i]]=a[coada_x[i]][coada_y[i]]+1;
			contor++;
			coada_x[contor]=coada_x[i]+1;
			coada_y[contor]=coada_y[i];
		}
		if(a[coada_x[i]-1][coada_y[i]]==0 && coada_x[i]-1>=1)
		{
			a[coada_x[i]-1][coada_y[i]]=a[coada_x[i]][coada_y[i]]+1;
			contor++;
			coada_x[contor]=coada_x[i]-1;
			coada_y[contor]=coada_y[i];
		}
	}
	
}	

Poti afisa matricea a in prima conditie sa vezi ce se formeaza in matrice
Pentru a reconstituii drumul pleci din a[n][m] care are valoarea x si cauti un vecin care are x-1 si il marchezi cu D... si cauti asa pana ajungi la cel care are valoarea 1 ...adica atunci cand ai ajuns la sosire...
 Sper ca ai inteles ceva...