problema labirintului backtracking

Problema labirintului backtracking

Se dă un labirint sub formă de matrice de m linii şi n coloane. Fiecare element al matricii reprezintă o cameră. Într-una din camerele labirintului se găseşte un om. Se cere să se afle toate soluţiile ca acel om să iasă din labirint, fără să treacă de două ori prin aceeaşi cameră.Se utilizeaza metoda backtracking.

#include<iostream.h>
#include<fstream.h>

int st[20][20],i,m,n,v[20][20],a[20][20];

void tipar(int k)
{for(i=1;i<=k;i++)
cout<<st[i][1]<<”  “<<st[i][2]<<”      “;
cout<<endl;}
int valid(int k)
{if(v[st[k][1]][st[k][2]]==0)
return 0;
for(i=1;i<k;i++)
if((st[k][1]==st[i][1])&&(st[k][2]==st[i][2]))
return 0;
return 1;
}
int solutie(int k)
{return((st[k][1]==1)||(st[k][1]==m)||(st[k][2]==1)||(st[k][2]==n));}
void bk(int k)
{int val;
for(val=1;val<=4;val++)
{st[k][1]=st[k-1][1]+a[val][1];
st[k][2]=st[k-1][2]+a[val][2];
if(valid(k))
if(solutie(k))
tipar(k);
else
bk(k+1);}}

void main()
{int j,k,r;
fstream f(“labirint.in”,ios::in);
f>>m>>n;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
f>>v[i][j];
for(i=1;i<=4;i++)
for(j=1;j<=2;j++)
f>>a[i][j];
cin>>k;cin>>r;
st[1][1]=k;
st[1][2]=r;
bk(2);}

 

Leave a Reply