Titlul: Drumul printr-o matrice cu obstacole ne punctiforme Scris de: niculae alexandru din Martie 15, 2011, 18:12:41 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 Titlul: Răspuns: Drumul printr-o matrice cu obstacole ne punctiforme Scris de: Oancea Catalin din Martie 15, 2011, 19:20:58 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). Daca nu stii inca nimic de algoritmul lui Lee poti sa imi dai un PM... te pot ajuta ... succes! :) Titlul: Răspuns: Drumul printr-o matrice cu obstacole ne punctiforme Scris de: niculae alexandru din Martie 15, 2011, 21:58:16 am auzit de algoritmul lee dar nu am nici cea mai vaga idee despe ce e si cum functioneza .. :fool:
Titlul: Răspuns: Drumul printr-o matrice cu obstacole ne punctiforme Scris de: Oancea Catalin din Martie 15, 2011, 22:10:29 Cod: int main() 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... :peacefingers: |