h2(#sectiune1). Introducere

În continuare vom prezenta _algoritmul lui Lee_, pentru cei care nu ştiu este _parcurgerea în lăţime_.
 
*Numele de Algoritmul lui Lee nu exista decat in limba romana fiind aparut probabil de la un profesor care l-a bagat in un manual de info din greseala.*
 
Acest algoritm este de fapt o particularizare a algoritmului menţionat mai sus, şi anume _parcurgerii în lăţime_. Este eficient, având o complexitate de $O(M*N)$, şi frecvent utilizat. 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 identic cu _parcurgerea în lăţime_ doar ca e aplicat pe o grila, nu pe un graf oarecare. Este eficient, având o complexitate de $O(M*N)$, şi frecvent utilizat. Acesta determină drumul minim de ieşire dintr-un labirint, sau în probleme asemănătoare.

h2(#sectiune2). Prezentare

_Cautarea in latime_ presupune doi paşi importanţi:

_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. În această coadă se pun, pentru fiecare pas, locurile care s-au marcat la punctul anterior.
# Se marchează cu numere consecutive toate locurile posibile prin care putem trece, parcurgând în ordine elementele cozii, până când nu mai putem marca, sau am ajuns la final.

h3. Rezolvare

După cum observaţi, este o aplicaţie a _cautarii in latime_. 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. În primul pas vom pune în coadă coordonatele locului de plecare, urmând apoi să parcurgem pe rând coada, până când nu mai există cale de ieşire sau am găsit una. Vă voi da un exemplu pentru a vă arata mai bine cum se marchează fiecare vecin în parte:

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. În primul pas vom pune în coadă coordonatele locului de plecare, urmând apoi să parcurgem pe rând coada, până când nu mai există cale de ieşire sau am găsit una. Vă voi da un exemplu pentru a vă arata mai bine cum se marchează fiecare vecin în parte:

|_. fişier intrare |_. fişier ieşire |_. explicaţii |
| $5$ $5$

$1$ $0$ $0$ $1$ $1$
$1$ $0$ $1$ $1$ $1$|6| $1$ $1$ $1$ $1$ $1$
$1$ _3_ _2_ _1_ $-1$

$1$ _4_ _3_ _2_ $1$

$1$ _4_ _3_ $1$ $1$

$1$ _5_ _4_ $1$ $1$
$1$ _6_ $1$ $1$ $1$|