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$