A. Consideratii teoretice
Se poate aplica un algoritm de tip "greedy" care va fi mai lent, dar va memora toate drumurile si va gasi si drumul de iesire minim.
Principiul este asemanator cu principiul lui Huygens din teoria undelor: "Un punct de pe o suprafata de unda este un punct de generare a altor unde (de aceeasi frecventa si amplitudine)".
B. Exemple
L: array [0..N-1, 0..M-1] of integer;
D: array [1..4, 1..2] of integer;
D[1,1] :=-1;
D[1,2] := 0;
D[2,1] := 0;
D[2,2] :=-1;
D[3,1] := 1;
D[3,2] := 0;
D[4,1] := 0;
D[4,2] := 1;
const D: array [1..4, 1..2] of integer=((-1,0), (0,-1), (1,0), (0,1));
var k,i,j : integer; stop : boolean; begin k:=1; i:=<valoarea punctului de plecare pe coordonata x>; j:=<valoarea punctului de plecare pe coordonata y>; L[i,j]:=k; { fixarea punctului de plecare }; repeat stop:=true; for i:=1 to N-2 do for j:=1 to N-2 do if L[i,j]=k then for DI:=1 to 4 do if L[i+D[DI,1], j+D[DI,2]] then begin L[i+D[DI,1], j+D[DI,2]]:=k+1; stop :=false; end; k:=k+1; until stop; end.
i:=<valoarea coordonatei x a punctului de iesire>; j:=<valoarea coordonatei y a punctului de iesire>; k:=L[i,j]; *afiseaza pe ecran punctul de plecare cu 'S' repeat *cauta vecinul de valoare k-1 => L[iurm,jurm] i:=iurm; j:=jurm; *afiseaza pe ecran pasul facut cu '+' k:=k-1; until k=1;
C. Teme