* 'Prezentare':algoritmul-lee#sectiune2
* 'Aplicaţia #1':algoritmul-lee#sectiune3
* 'Aplicaţia #2':algoritmul-lee#sectiune4

* 'Aplicaţia #3':algoritmul-lee#sectiune5
* 'Aplicaţia #4':algoritmul-lee#sectiune6

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 _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

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:

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$|

h3. Rezolvare

Această problemă se rezolvă cu _algoritmul lui Lee_, doar că în coadă vom pune iniţial nu o coordonată, ci toate coordonatele paznicilor. Pentru asta se citesc ca şir de caractere fiecare caracter în parte, şi se convertesc acestea (la citire) în numere astfel: zidurile (#) vor fi notate cu $-2$, paznicii (P) cu $-1$, iar căile libere cu $0$. După executarea algoritmului, se verifică şi se înlocuiesc cifrele de $0$ cu $-1$ (pentru că în problemă ne cere să afişăm cu $-1$ locurile care nu au fost vizitate), iar cifrele de $-1$ (reprezentând paznicii) cu $0$. Aveţi un exemplu de citire transpus în pseudocod:

Această problemă se rezolvă cu _algoritmul lui Lee_, doar că în coadă vom pune iniţial nu o coordonată, ci toate coordonatele paznicilor. Pentru asta se citesc ca şir de caractere fiecare caracter în parte, şi se convertesc acestea (la citire) în numere astfel: zidurile $(#)$ vor fi notate cu $-2$, paznicii $(P)$ cu $-1$, iar căile libere cu $0$. După executarea algoritmului, se verifică şi se înlocuiesc cifrele de $0$ cu $-1$ (pentru că în problemă ne cere să afişăm cu $-1$ locurile care nu au fost vizitate), iar cifrele de $-1$ (reprezentând paznicii) cu $0$. Aveţi un exemplu de citire transpus în pseudocod:

==code(cpp)|
citeşte m
   pentru i=1,m
        pentru j=1,m
         început

            citeşte s
            dacă (s=='#') ct[i][j]=-2
            altfel dacă (s=='.') ct[i][j]=0;
            altfel dacă (s=='P') ct[i][j]=-1;
            dacă (ct[i][j]==-1)

            citeşte s                         //variabila cu care citim caracterele pentru a le putea converti
            dacă (s=='#') ct[i][j]=-2         //convertim caracterul în cifre
            altfel dacă (s=='.') ct[i][j]=0;  //-----------------------------
            altfel dacă (s=='P') ct[i][j]=-1; //-----------------------------
            dacă (ct[i][j]==-1)               //verificăm dacă există un paznic

             început

                q[l].st=i;
                q[l].dr=j;
                l++;

                q[l].st=i;                    //punem paznicul în coadă
                q[l].dr=j;                    //-----------------------
                l++;                          //contorul cu care numărăm paznicii

             sfârşit(dacă)
        sfârşit(pentru)

   q1=l;

   q1=l;                                      //contorul pe care îl folosim pentru a număra şi a pune în coadă locurile vizitate

==

h2(#sectiune5). Aplicaţia #3 -> 'Insule':http://infoarena.ro/problema/insule

bq. Dată fiind harta arhipelagului să se determine câte insule aparţin fiecărei ţări, precum şi lungimea minimă a unui pod care să satisfacă condiţiile din enunt.
 
h3. Rezolvare
 
Pentru determinarea numărului de insule pentru fiecare ţară, se utilizează altgoritmul 'FLOOD FILL':http://en.wikipedia.org/wiki/Flood_fill. Acest algoritm este algoritmul lui Lee, doar simplificat. Pentru partea cu podul, se utilizează algoritmul lui Lee, doar că în coadă vom pune zonele de  ape, care au vecini o ţară $R$. Se parcurge coada până găsim o zonă de apă care are vecin o ţară $G$.
 
h2(#sectiune6). Aplicaţia #4 -> 'Alee':http://infoarena.ro/problema/alee
 
 
bq. Scrieti un program care sa determine numarul minim de dale necesare pentru construirea unei alei continue de la o poarta la cealalta.
 
h3. Rezolvare
 
Această problemă se rezolvă cu algoritmul lui Lee, iniţializând toată matricea cu $-2$, apoi pe parcurs ce citim poziţiile modificăm matricea cu $-1$, adică pomi, iar la sfârşit punem în coadă intrarea, o marcăm cu $-1$, iar ieşirea o marcăm cu $-3$. Parcurgem elementele din coadă până dăm de poarta de ieşire.