Structuri de Date

1.Enuntul problemei

Traseu in labirint

Fie un labirint(o retea dreptunghiulara)-cu cellule ocupate (x) si libere (*).Fie un robot (R) in acest labirint.

X * X X * * *

* X * * X * *

* * * * * * *

* * * R * * X

* X * * * * X

* * * * X * *

* X * X * * *

(a)Testati daca R poate iesi din labirint (poate ajunge la margine?)

(b)Determinati un drum pentru iesirea din labirint (daca exista).

(c)Determinati un drum de lungime minima pentru iesire (daca exista).

Se va folosi :Stiva (Coada),Coada cu prioritati.

2. Specificare

Acest program rezolva problema labirintului folosind metode backtracking generalizat.

Stiva este reprezentata sub forma unui tablou cu 2 coloane, prima reprezentand linia si ce-a de-a doua coloana.

In tabloul minim se retine configuratia stivei pentru cel mic drum gasit pana in momentul respectiv.

Tabloul deplasare retine cele patru moduri de deplasare la un moment dat : SUD, NORD, EST, VEST.

Vectorul l retine labirintul, fiecare pozitie libera fiind codificata cu 1 , iar zidul fiind codificat cu 0.

n =nr de linii

m=nr de coloane

lmin – lungimea drumului minim

Citirea labirintului se face din fisier astfel :

-pe prima linie – nr n de linii si nr m de coloane

- pe urmatoarele n linii – se afla liniile labirintului

- ultimele 4 linii contin modul de deplasare in labirint : VEST, EST, NORD, SUD

Procedura CITIRE – realizeaza citirea din fisier

Functie VALID – testeaza daca o configuratie a stivei este sau nu valida returnand true daca este valida si false in caz contrar. Se verifica daca pozitia curenta a mai fost sau nu vizitata in prealabil ( pozitiile anterioare sunt retinute in stiva de pe pozitia 1 pe pozitia p-1). Daca a mai fost vizitata, atunci configuratia nu mai este valida.

Daca pozitia curenta in labirint nu este libera, (este zid), atunci configuratia nu este valida, deci validintoarce valoarea false.

Functia FINAL – testeaza daca solutia retinuta in stiva este finala, adica daca s-a iesit din labirint.

O solutie este finala daca s-a ajuns la iesirea din labirint, adica linie este 1(prima) sau n(ultima) sau coloana este 1(prima) sau m (ultima).

Procedura TIPAR – tipareste solutia, adica configurtia stivei si in cazul in care s-a gasit o solutie (un drum mai mic), atunci acesta se retine in min si lungimea acestuia in lmin.

Procedura MINIM – tipareste solutia minima (cel mai scurt drum de iesire din labirint)

Procedura BACKTRACKING.De pe pozitia curenta se incearca deplasarea in unul din cele patru moduri posibile. Daca solutia obtinuta este valida, atunci daca e finala, se tipareste. In caz contrar, (e valida ,dar nu e finala) se incearca o noua deplasare ( se apeleaza recursiv pentru nivelul p+1).

In cazul in care solutia nu e valida, fiind vorba de o procedura recursiva, aceasta se intoarce din auto apel la configuratia anterioara ( pastrata in heap).

Algoritm backtracking

Pentru i de la 1 la 4 executa

pt [p,1]‹st [p-1,1]+depl [i,1]

pt [p,2]‹st [p-1,2]+depl [i+2]

daca solutia este valida

daca solutia este finala atunci tipareste solutia altfel

apeleaza recursiv pentru p+1

sfarsit daca

sfarsit daca

sfarsit pentru