Backtracking in plan

Backtracking in plan

Fie urmatoare problema: un soricel se gaseste intr-un labirint de forma dreptunghiulara cu m linii si n coloane. Peretii sunt marcati cu 1 si culoarele cu 0. Se cunosc coordonatele initiale ale soricelului: Li, Ci. Sa se determine toate posibilitatile pe care le are soricelul pentru a iesi din labirint. Soricelul poate avansa pe 4 directii cate o celula (sus, dreapta , jos, stanga).

O astfel de problema presupune o abordare Backtracking in plan. Traseul soricelului va fi retinut de un vector cu doua campuri: coordonatele x si y. Vom defini un tip struct:

struct pozitie

{int x,y;};

si vom declara un vector care retine drumul: pozitie d[50];

Pentru generarea unui drum vom defini un subprogram recursiv oid ies(int x,int y) care primeste ca parametri coordonatele unei componente din matrice. Initial se apeleaza pentru coordonatele initiale ale soricelului. O componenta din matrice va putea apartine drumului daca evident este culoar (a[x][y]=0). O celula a matricii determinata ca apartinand drumului se marcheaza cu 2 (pentru a preveni ciclarile):

a[x][y]=2;

Se incarca valoarea corespunzatoare in vectorul d pe nivelul curent:

d[k].x=x;

d[k].y=y;

De fiecare data cand s-a determinat o noua celula ca apartinand drumului se determina daca s-a ajuns la solutie (conditie care difera de la o problema la alta).

In cazul probemei noastre se iese din labirint cand se ajunge la linia 0 sau coloana 0 sau linia m+1 sau coloana n+1. testul este:

if((x<1)||(x>m)||(y<1)||(y>n))

tipar(k);

In caz afirmativ se tipareste (se afiseaza vectorul d si/sau matricea a) altfel (daca solutia este incompleta) se incearca parcurgerea, pe rand, a celor 4 celule alaturate. Acest lucru se realizeaza prin autoapelul functiei ies pe cele patru directii:

ies(x-1,y);

ies(x,y+1);

ies(x+1,y);

ies(x,y-1);

Observatie: vectorul d functioneaza ca o stiva cu doua campuri.

La revenire din apel se elibereaza celula pentru a o putea accesa si in cadrul altor prelucrari: a[x][y]=0 si se elibereaza componenta drumului k=k-1 (practic se coboara in stiva).

void ies(int x,int y)

{if(a[x][y]==0)

{k++;

a[x][y]=2;

d[k].x=x;

d[k].y=y;

if((x<1)||(x>m)||(y<1)||(y>n))

tipar(k);

else

{ies(x-1,y);

ies(x,y+1);

ies(x+1,y);

ies(x,y-1);

}

a[x][y]=0; //la revenire din apel demarchez celula pentru a o putea

//accesa si in cadrul altei prelucrari

k--; //eliberez componenta din vectorul drumului

}

Fie urmatorul labirint: m=6 n=10 Li=4, Ci=3

1 1 1 1 0 1 1 1 1 1

1 1 0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 0 1 1

Solutiile vor fi:

solutia 1

(4,3) (4,4) (4,5) (3,5) (2,5) (1,5) (0,5)

1 1 1 1 2 1 1 1 1 1

1 1 2 2 2 0 0 0 0 0

1 1 1 1 1 1 1 0 1 1

solutia 2

(4,3) (4,4) (4,5) (4,6) (4,7) (4,8) (4,9) (4,10) (4,11)

1 1 1 1 0 1 1 1 1 1

1 1 2 2 2 2 2 2 2 2

1 1 1 1 1 1 1 0 1 1

solutia 3

(4,3) (4,4) (4,5) (4,6) (4,7) (4,8) (5,8) (6,8) (7,8)

1 1 1 1 0 1 1 1 1 1

1 1 2 2 2 2 2 2 0 0

1 1 1 1 1 1 1 2 1 1

Programul complet este:

#include<fstream.h>

#include<conio.h>

struct pozitie

{int x,y;};

int a[20][20];//labirintul

int k,n,m,Li,Ci,nr_sol;

pozitie d[50];

void afis_mat() //afiseaza matricea

{cout<<endl;

for(int i=1;i<=m;i++)

{for(int j=1;j<=n;j++)

cout<<a[i][j]<<" ";

cout<<endl;}

}

void tipar(int k) //tipareste vectorul drum

{nr_sol++;

cout<<"solutia "<<nr_sol<<endl;

for(int i=1;i<=k;i++)

cout<<"("<<d[i].x<<','<<d[i].y<<") ";

afis_mat();

getch();

cout<<endl;}

void ies(int x,int y) //genereaza drumul

{if(a[x][y]==0)

{k++;

a[x][y]=2;

d[k].x=x;

d[k].y=y;

if((x<1)||(x>m)||(y<1)||(y>n))

tipar(k);

else

{ies(x-1,y);

ies(x,y+1);

ies(x+1,y);

ies(x,y-1);

}

a[x][y]=0; //la revenire din apel demarchez celula pentru a o putea

//accesa si in cadrul altei prelucrari

k--;//eliberez componenta din vectorul drumului

}

void citire()

{ fstream f;

f.open("labir.txt",ios::in);

if(f)

cout<<"ok";

else

cout<<"eroare la deschidere";

//Citesc matricea ce reprezinta labirintul

f>>m>>n;

for(int i=1;i<=m;i++)

for(int j=1;j<=n;j++)

f>>a[i][j];

f>>Li>>Ci; //coordonatele punctului in care se afla soricelul

}

void main()

{clrscr();

k=0;

citire();

ies(Li,Ci);

afis_mat();

getch();

}

Probleme propuse:

1. aceeasi problema ca in exemplu cu diferenta ca soricelul poate avansa in celule alaturate pe cele 8 directii posibile

2. Un soricel se gaseste intr-un labirint de forma dreptunghiulara cu m linii si n coloane. Peretii sunt marcati cu 1 si culoarele cu 0. Se cunosc coordonatele initiale ale soricelului: Li, Ci. Sa se determine toate posibilitatile pe care le are soricelul pentru a iesi ajunge la cascaval. Se cunosc coordonatele cascavalului: Lf,Cf.

3. Aceeasi problema ca la 2 cu diferenta ca se afiseaza doar cea mai scurta solutie.

4. Un labirint dreptunghiular cu m linii si n coloane contine culoare (reprezentate prin 0) si pereti (reprezentati prin -1). Se dau coordonatele initiale ale unui soricel si coordonatele finale , unde trebuie sa ajunga. Pe culoare se gasesc bucati de branza pt care se cunoaste greutatea in grame.

a) Sa se genereze toate solutiile., pt fiecare se afiseaza cantitatea consumata

b) Sa se afiseze soultia cea mai „consistenta” Indicatie: se vor marca cu -2 celulele parcurse si se vor retine in vectorul drum inclusiv cantitatea condumata. Matricea se borda cu pereti (-1).

5. Pe o tabla de forma dreptunghiulara se afla un cal. Se cunosc coordonatele initiale ale calului. Acesta trebuie sa ajunga intr-o pozitie finala sarind numai sub forma sariturii calului. Stiind ca numai anumite celule sunt permise sariturii (acestea sunt marcate) sa se determine ce posibilitati sunt ca sa se ajunga in pozitia finala.

6. Romeo si Julieta se gasesc intr-un labirint (se cunosc culoarele si peretii si coordonatele celor doi indragostiti).

a)Exista posibilitatea ca Romeo sa ajunga la Julieta?

b)in cazul in care cei doi se indreapta simultan unul catre celalat pentru fiecare solutie se va afisa locul intalnirii (coordonatele celulelor alaturate sau celulei comune de intalnire)