Buna ziua tuturor! Am de facut o problema care se rezolva cu algoritmul lui Lee, doar ca nu inteleg deloc cum se rezolva…
Enunt: Se dă o matrice cu M linii şi N coloane. Ştiind locul de plecare, marcat cu -1, se cere să se determine drumul de lungime minimă până la o ieşire, iar in caz că nu există, se va afişa -1.
Multumesc anticipat!
wraith99user (0)
Algoritmul lui Lee reprezinta ceea ce se cheama in literatura de specialitate ca BFS(breadth first search) sau parcurgere in latime a grafului. Se porneste dintr-un nod de start care il bagam intr-o coada. Apoi cat timp coada nu e vida scoatem ce avem inauntru` ei (adica primul element si-l marcam ca fiind vizitat, pentru ca coada functioneaza dupa principiul FIFO-first in first out). Apoi cauti toti vecinii acestuia care au inca distanta infinit fata de acel element). La inceput toate elementele vor fi la distanta infinita fata de toate celelalte elemente adica vei avea o matrice plina de infinit un singur element va fi -1 acela de pe linia si coloana de start. Distanta o egalezi cu 0 (tii un contor) si bagi toti vecinii nevizitati in coada. Apoi repeti procedeul pana gasesti iesirea din matrice. (Cum scoti un element din coada il marchezi ca vizitat) E clar? sau vrei si un exemplu?
As vrea eu un exemplu, daca se poate.
Multumesc.
@xor_NTG vrei si un grafic… sau il faci singur? Adica iti dau nr de puncte nr de arce si descrierea fiecarui arc… si trasezi graficul singur sau vrei sa-l si desenez? Daca vrei cu grafic cu tot… o sa dureze ceva mai mult… o zi doua… depinde cat imi ia sa ma eliberez… lucrez intr-un program mai special sa zicem de trasat grafuri… si ma cam mananca la timp de fiecare data cand desenez un graf… ce sa-i faci nu se poate face pocnind din degete… O sa pun si explicatiile cu parcurgere cu tot… mai intai imi spui daca ai de gand sa astepti graficu` sau il faci singur?
Ma intereseaza doar parcurgerea. Cu graficul ma pot juca eu. Imi trebuie doar codul, eventual optimizat, asa cum iti place tie.