* '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

$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

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.

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.