Cel mai scurt drum printr-un labirint
Un robot de depozit pornește din punctul S și trebuie să ajungă la raftul E, ocolind stâlpii #. Care este numărul minim de pași? Combini cele două idei din lecțiile anterioare: grila ca graf și BFS pentru cel mai scurt drum.
Problema
Labirintul este o listă de texte de aceeași lungime: S = start, E = ieșire, # = zid, . = liber. La fiecare pas robotul se mută într-o celulă vecină (sus, jos, stânga, dreapta). Returnează numărul minim de pași, sau -1 dacă ieșirea nu poate fi atinsă.
Scrie funcția pasi_minimi(labirint) care returnează numărul minim de pași de la S la E (4 direcții, # = zid), sau -1 dacă nu există drum, folosind BFS cu o coadă deque.
- Găsește poziția lui S parcurgând grila.
- Pune în coadă ((r, c), 0) și marchează startul ca văzut.
- La fiecare scoatere: dacă celula este E, întoarce pașii; altfel adaugă vecinii liberi și nevăzuți cu pasi + 1.
- Trebuie să apară: 8, -1, 1, 16.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Arbori, grafuri și heap.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan