_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. Vă voi da un exemplu pentru a vă arata mai bine cum se marchează fiecare vecin în parte:

# 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.
 
h2(#sectiune3). Aplicaţia #1 -> Problema Labirintului
 
bq. Se dă o matrice cu M linii şi N coloane. Ştiind locul de plecare, marcat cu $-1$, 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$
 
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. Î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. Aveţi 'aici':algoritmul-lee?lee-lab.cpp o sursă cu acest algoritm implementat în C++, sau 'aici':algoritmul-lee?lee-lab.pas o sursă implementată în Pascal. 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$ {**5**} {**4**} $1$ $1$
$1$ {**6**} $1$ $1$ $1$ |

h2(#sectiune3). Aplicaţia #1 -> Problema Labirintului
 
bq. Se dă o matrice cu M linii şi N coloane. Ştiind locul de plecare, marcat cu $-1$, 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$
 
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. Î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. Aveţi 'aici':algoritmul-lee?lee-lab.cpp o sursă cu acest algoritm implementat în C++, sau 'aici':algoritmul-lee?lee-lab.pas o sursă implementată în Pascal.
 

h2(#sectiune4). Aplicaţia #2 -> 'Muzeu':http://infoarena.ro/problema/muzeu
bq. Un muzeu are forma patratica si contine N*N camere ce pot fi vizitate. Unele camere sunt deschise si contin opere de arta, altele sunt inchise (sunt folosite pentru alte scopuri). In unele din camerele libere, se afla paznici. Directorul muzeului se teme de eventualitatea unei spargeri si de aceea doreste sa evalueze cat de bine au fost asezati paznicii in camerele libere. Mai precis, el doreste sa afle, pentru fiecare camera libera, care este distanta minima pana la cel mai apropiat paznic (numarul minim de camere prin care trebuie sa intre un paznic pentru a ajunge la camera respectiva). Paznicii se pot deplasa numai in camerele libere din Nord, Est, Sud sau Vest (cu conditia sa nu paraseasca muzeul).