h2(#sectiune1). Introducere

În continuare vom prezenta _algoritmul lui Lee_, pentru cei care nu ştiu este _parcurgerea în lăţime_. Acest algoritm este de fapt o particularizare a algoritmului menţionat mai sus, şi anume _parcurgere în lăţime_. Este foarte util, având o complexitate de $O(M*N)$, şi frecvent uitilizat. Acesta determină drumul minim de ieşire dintr-un labirint, sau în probleme asemănătoare.

În continuare vom prezenta _Algoritmul lui Lee_, pentru cei care nu ştiu este aşa-numita _Parcurgere în Lăţime_. Acest algoritm este de fapt o implementare a algoritmului menţionat mai sus, şi anume _Parcurgere în Lăţime_. Este foarte util, având o complexitate de $O(M*N)$, şi frecvent uitilizat. Acesta determină drumul minim de ieşire dintr-un labirint, sau în probleme asemănătoare.

h2(#sectiune2). Prezentare

h2(#sectiune3). Aplicaţie -> Problema Labirintului

bq. Se dă o matrice cu M linii şi N coloane. Ştiind locul de plecare, se cere să se determine drumul de lungime minimă până la o ieşire, iar in caz că nu există, se va afişa $-1$

bq. Ştiind locul de plecare, se cere să se determine drumul minim până la o ieşire, iar in caz că nu există, se va afişa $-1$

h3. Rezolvare

După cum observaţi, este o aplicaţie a _algoritmului lui Lee_. Această problemă se poate rezolva şi cu metoda 'backtracking':http://en.wikipedia.org/wiki/Backtracking, dar această metodă nu este una eficientă, complexitatea fiind $O(4^(M*N)^)$, sau $O(3^(M*N)^)$ după caz, ceea ce este foarte mult.

După cum observaţi, este o aplicaţie a _Algoritmului lui Lee_. Această problemă se poate rezolva şi cu metoda 'backtracking':http://en.wikipedia.org/wiki/Backtracking, dar această metodă nu este una eficientă, complexitatea fiind $O(4^(M*N)^)$, sau $O(3^(M*N)^)$ după caz, ceea ce este foarte mult.