Backtracking Labirint

#include <iostream>

#include <fstream>

// Moraru-backtracking generalizat pg.221 problema 51

using namespace std;

int sol[100][2],vecini[5][3],n,m,i,j,x,y,va,mo;

char l[50][50];

FILE f;

void initializari()

{

int i,j;

ifstream f("iepuras.dat");

f>>n>>m;

for(i=1;i<=n;i++)

{

for(j=1;j<=m;j++)

f>>l[i][j];// el. matrici sunt A-liber, M-morcov, V-varza, Z-zid, L-lup//

}

for(i=1;i<=4;i++)

f>>vecini[i][1]>>vecini[i][2];

sol[0][1]=7;//pozitia initiala a iepurasului

sol[0][2]=6;

}

void afis_date()

{

int i,j;

cout<<"datele din fisier sunt:n";

cout<<"n="<<n<<" m="<<m;

cout<<"n matricea labirintului n";

for(i=1;i<=n;i++)

{

for(j=1;j<=m;j++)

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

cout<<"n";

}

cout<<"n perechile de vecini sunt: n";

for(i=1;i<=4;i++)

cout<<vecini[i][1]<<" "<<vecini[i][2]<<"n";

}

void tipar (int p)

{

int j,i0,j0;mo=0;va=0;

for(j=0;j<=p;j++)

cout<<"("<<sol[j][1]<<","<<sol[j][2]<<") ";

for(j=0;j<=p;j++)

{ i0=sol[j][1];j0=sol[j][2];

if(l[i0][j0]=='M') mo++;// nr. morcovi culesi de iepure

}

for(j=0;j<=p;j++)

{ i0=sol[j][1];j0=sol[j][2];

if(l[i0][j0]=='V') va++;//nr. varza culeasa de iepure

}

cout<<"n morcovi adunati :"<<mo<<" ";

cout<<"n varza :"<<va;

cout<<"n";

}

int valid(int p)

{

int i,ok,i0,j0; ok=0;

i0=sol[p][1];j0=sol[p][2];

if(l[i0][j0]=='A' || l[i0][j0]=='M' || l[i0][j0]=='V')

{

ok=1;

for(i=0;i<=p-2;i++)

if(sol[p][1]==sol[i][1] && sol[p][2]==sol[i][2]) ok=0;

} return ok;

}

void bktr(int p)

{

int pval;

for(pval=1;pval<=4;pval++)

{

sol[p][1]=sol[p-1][1]+vecini[pval][1];

sol[p][2]=sol[p-1][2]+vecini[pval][2];

if (valid(p))

if(sol[p][1]==1 || sol[p][1]==n || sol[p][2]==1 ||sol[p][2]==n ) tipar(p);

else bktr(p+1);

}

}

int main()

{

initializari();

afis_date();

bktr(1);

return 0;

}

backtracking generalizat