Algoritmul lui Lee — drumul minim în labirint

De ce contează?

Pune o picătură de cerneală pe o hartă de labirint: ea se întinde uniform în toate direcțiile, ocolind pereții, și ajunge la orice cameră pe drumul cel mai scurt. Algoritmul lui Lee face exact această „inundare” controlată.

Ce rezolvă algoritmul lui Lee?

Ai o matrice (un teren) cu celule libere și obstacole. Vrei distanța minimă (număr de pași) de la o celulă de start la o destinație, mergând doar pe celule libere, în 4 direcții.

Lee este pur și simplu un BFS pe matrice: tratezi fiecare celulă liberă ca pe un nod, iar celulele vecine ca pe muchii.

Ideea: inundare nivel cu nivel

Pornești de la start cu distanța 0. Pui startul în coadă. Repetat: scoți o celulă, îi marchezi vecinii liberi nevizitați cu distanța celulei curente + 1 și îi pui în coadă.

O linie din matricea de distanțe: start are 0 (vecin), # = obstacol. Distanțele cresc cu 1 la fiecare pas de la start.

Observația-cheie

Coada (FIFO) e esența corectitudinii: celulele apropiate de start ies primele, deci umplerea se face strict în ordinea distanței. Prima atingere a destinației = drum minim.

Vectorii de direcție

Ca să nu scrii patru cazuri separate pentru cei 4 vecini, folosești doi vectori mici:

int dl[] = {-1, 0, 1, 0};   // sus, dreapta, jos, stanga (linie)
int dc[] = { 0, 1, 0,-1};   // coloana

Vecinul k al celulei (i, j) este (i + dl[k], j + dc[k]).

Implementare C++

#include <iostream>
#include <queue>
using namespace std;

int n, m;
int dist[105][105];   // -1 = nevizitat, altfel distanta
int grid[105][105];   // 0 = liber, 1 = obstacol

int dl[] = {-1, 0, 1, 0};
int dc[] = { 0, 1, 0,-1};

int lee(int li, int lj, int di, int dj) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) dist[i][j] = -1;

    queue<pair<int,int>> q;
    dist[li][lj] = 0;
    q.push({li, lj});

    while (!q.empty()) {
        auto cel = q.front(); q.pop();
        int i = cel.first, j = cel.second;
        for (int k = 0; k < 4; k++) {
            int ni = i + dl[k], nj = j + dc[k];
            // in interior, liber si nevizitat?
            if (ni >= 0 && ni < n && nj >= 0 && nj < m
                && grid[ni][nj] == 0 && dist[ni][nj] == -1) {
                dist[ni][nj] = dist[i][j] + 1;   // un pas mai departe
                q.push({ni, nj});
            }
        }
    }
    return dist[di][dj];   // -1 daca destinatia e inaccesibila
}

int main() {
    n = 3; m = 3;
    int g[3][3] = {{0,0,0},{1,1,0},{0,0,0}};
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) grid[i][j] = g[i][j];

    cout << lee(0, 0, 2, 0) << "\n";  // 4 (ocoleste peretele)
    return 0;
}

De ce verificăm dist[ni][nj] == -1? Ca să nu reintrăm într-o celulă deja atinsă — altfel am pune aceeași celulă de mai multe ori în coadă și am pierde proprietatea de drum minim.

Complexitate

Mărime	Timp	Spațiu
matrice n × m	O(n · m)	O(n · m)

Fiecare celulă intră în coadă cel mult o dată; pentru fiecare verifici 4 vecini.

Greșeli frecvente

Greșeli frecvente de concurs:

Ieșire din matrice: verifică ni, nj în limite ÎNAINTE de a accesa grid[ni][nj].
Stivă în loc de coadă: cu o stivă obții o parcurgere în adâncime — distanțele NU mai sunt minime.
Marcare târzie: marchează dist când pui în coadă, nu când scoți; altfel duplici celule.
Inițializare: dacă uiți să resetezi dist cu -1 între rulări, ai rămășițe din apelul anterior.

Vizualizare

Urmărește inundarea matricei, nivel cu nivel, din celula de start:

Indiciu

Observă cum toate celulele la aceeași distanță se colorează „în același val”. Folosește ← / → pentru a vedea fiecare nivel.

Recapitulare

Lee = BFS pe matrice; coada garantează că prima atingere a unei celule e pe drum minim.
Vectorii de direcție dl/dc generează cei 4 vecini compact, într-un for.
Verifică limitele și marchează vizitarea la inserare — O(n · m) timp și spațiu.