De ce contează?
Arunci o piatră într-un lac liniștit. Din punctul de impact pleacă un cerc, apoi încă unul mai mare, apoi altul — unde concentrice care ating apa tot mai departe, toate în același ritm. Prima undă care atinge o frunză plutitoare a ajuns acolo pe cel mai scurt drum posibil; nicio undă de mai târziu n-o poate atinge mai repede. Algoritmul lui Lee inundă exact așa o matrice: de la sursă, val cu val, până atinge ținta — iar primul val care o atinge îi spune distanța minimă.
Intuiția
Ai o grilă (un labirint) cu celule libere și obstacole. Vrei numărul minim de pași
de la o celulă-sursă la o celulă-țintă, mișcându-te doar sus, jos, stânga, dreapta.
Ideea: pornești din sursă cu distanța 0, marchezi toți vecinii liberi cu 1,
vecinii lor încă nemarcați cu 2, și așa mai departe. Fiecare „inel” de celule cu
aceeași distanță e o undă care se propagă. Pentru că extinzi mereu mai întâi celulele
cele mai apropiate, prima dată când atingi o celulă o atingi pe drumul cel mai scurt.