Etichete: nicio etichetă

Problemă: Se dă o matrice binară, reprezentând harta unui teren (labirint, clădire, tablă de joc, etc.), în care valorile 0 reprezintă zone libere, iar cele egale cu 1 reprezintă obstacole. Într-o zonă aflată la coordonate cunoscute se află un mobil, care se poate deplasa prin matrice, trecând din zona curenta în una din cele patru zone vecine de pe aceeași linie sau aceeași coloană, dacă este liberă. Să se identifice zonele în care poate să ajungă mobilul.

Problema enunțată mai sus face parte din categoria Algoritmilor de umplere sau FILL, iar prezentul articol este consacrat acestor algoritmi!

Citește mai departe:

Algoritmi de umplere - generalități

Pentru a identifica zonele în care poate ajunge mobilul, le vom marca în matrice cu o altă valoare (de exemplu cu 2); vom face operația pas cu pas, pe următorul principiu: dacă o anumită zonă a matricei este zonă curentă (mobilul se află în acea zonă), atunci acea zonă va fi marcată ca vizitată, iar vecinii acelei zone care sunt liberi și nu au fost vizitați vor deveni la rândul lor zone curente. …

Fill recursiv

Operația de umplere poate fi sistematizată astfel: …

Fill cu coadă

Algoritmul de umplere (FILL) pe matrice funcționează pe ideea: marcăm elementul curent și analizăm vecinii liberi și nemarcați ai acestuia. Pentru a gestiona ordinea în care se face acest lucru putem folosi recursivitatea sau putem folosi o structură de date de tip coadă – queue. Această metodă are o serie de avantaje, fiind de regulă mai rapidă. …