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

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.