Algoritmul lui Lee

Intuiția

Ai o hartă-grilă (un labirint): unele celule sunt libere, altele sunt ziduri. Pornești dintr-o celulă de start și vrei numărul minim de pași până la o destinație, mișcându-te doar sus / jos / stânga / dreapta. Ideea-cheie e că celulele se umplu în val: toate celulele aflate la distanța d de start primesc valoarea d înainte ca vreuna aflată la d+1 să fie atinsă. Fiecare celulă nouă moștenește distanța vecinului din care a fost atinsă, plus 1. Pentru că valul se lățește uniform, prima atingere a oricărei celule e garantat pe drumul cel mai scurt. Acesta este pur și simplu BFS pe o matrice. Spre deosebire de o simplă umplere (fill), care doar marchează ce celule sunt accesibile, Lee etichetează fiecare celulă cu distanța minimă până la ea — de aceea îți dă numărul minim de pași, nu doar „se poate ajunge sau nu".

Vezi cum funcționează

Urmărește cum pornește valul din start (0,0) cu distanța 0 și se lățește celulă cu celulă: inelul de distanță 1, apoi 2, apoi 3... ocolind obstacolele. Observă că destinația (3,3) se colorează exact când valul ajunge la distanța 6.

Algoritmul pas cu pas

Fie matricea 4 x 4 de mai jos. . e celulă liberă, # e obstacol. Start în (0,0), destinație în (3,3). Mișcări permise: sus, jos, stânga, dreapta.

Pornim valul din (0,0) cu distanța 0 și îl lățim inel cu inel. La fiecare pas luăm din coadă toate celulele de aceeași distanță și le marcăm vecinii liberi cu distanța următoare. Iată distanțele rezultate, linie cu linie (# = obstacol):

Urmărește cum cresc valurile: distanța 0 e doar (0,0); distanța 1 sunt (0,1) și (1,0); distanța 2 sunt (0,2) și (2,0); și tot așa. Inelul de distanță 6 conține o singură celulă — chiar destinația.

Implementare C++

BFS clasic pe matrice: o coadă de perechi (linie, coloană), vectorii dl/dc pentru cele 4 direcții, și matricea dist inițializată cu -1. Pentru fiecare vecin verificăm în această ordine: margini valide, nu e obstacol, nu e vizitat.

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

int L = 4, C = 4;             // dimensiunile matricei
int mat[4][4] = {             // 0 = liber, 1 = obstacol
    {0, 0, 0, 0},
    {0, 1, 0, 0},
    {0, 0, 1, 0},
    {0, 0, 0, 0}
};
int dist[4][4];               // distanta minima de la start; -1 = nevizitat

// cele 4 directii: sus, jos, stanga, dreapta
int dl[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

int lee(int linStart, int colStart, int linDest, int colDest) {
    // initializez toata matricea de distante cu -1 (nevizitat)
    for (int i = 0; i < L; i++)
        for (int j = 0; j < C; j++)
            dist[i][j] = -1;

    queue<pair<int,int>> coada;
    dist[linStart][colStart] = 0;       // start are distanta 0
    coada.push({linStart, colStart});

    while (!coada.empty()) {
        int lin = coada.front().first;
        int col = coada.front().second;
        coada.pop();

        // incerc cei 4 vecini
        for (int k = 0; k < 4; k++) {
            int linNou = lin + dl[k];
            int colNou = col + dc[k];

            // intai margini valide, apoi obstacol, apoi nevizitat
            if (linNou >= 0 && linNou < L && colNou >= 0 && colNou < C
                && mat[linNou][colNou] == 0 && dist[linNou][colNou] == -1) {
                dist[linNou][colNou] = dist[lin][col] + 1;   // val + 1
                coada.push({linNou, colNou});
            }
        }
    }

    return dist[linDest][colDest];      // -1 daca destinatia e de neatins
}

int main() {
    cout << lee(0, 0, 3, 3) << "\n";    // afiseaza: 6
    return 0;
}

Prima atingere a fiecărei celule e finală, de aceea nu rescriem niciodată o distanță deja setată: condiția dist[linNou][colNou] == -1 joacă dublu rol — și marcaj de „vizitat", și garanție că păstrăm valoarea minimă.

Complexitate

L = numărul de linii, C = numărul de coloane. Fiecare celulă intră în coadă cel mult o dată (după prima atingere e marcată), iar pentru fiecare îi verificăm cei 4 vecini.