h1. Algoritmul lui Lee
 
(Categoria _Algoritmi_, Autor _Simoiu Robert_)
 
(toc){width: 10em}*{text-align:center;} *Conţinut*
* 'Sectiunea 1':documentatie/structura-articol#sectiune1
* 'Sectiunea 2':documentatie/structura-articol#sectiune2
* 'Sectiunea 3':documentatie/structura-articol#sectiune3
 
h2(#sectiune1). Introducere
 
Î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
 
_Algoritmul lui Lee_ presupune doi paşi importanţi:
 
# Primul şi poate cel mai important pas este folosirea unei **Cozi**, sub forma unui vector de structuri (de preferabil), care va menţine toţi paşii pe care o să-i facem de acum în colo.
# Se marchează cu numere consecutive toate locurile posibile prin care putem trece, mergând din **coadă** în **coadă**, până când nu mai putem marca, sau am ajuns la final. În coadă vom băga toate locurile pe care le marcăm, verificând pentru fiecare în parte, la rândul lor, locurile pe care le putem marca.
 
h2(#sectiune3). Aplicaţie -> Problema Labirintului
 
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.
 
 
 

h1. Algoritmul lui Lee