Extras din laborator
#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;
}
Conținut arhivă zip
- Backtracking Labirint
- back_iepure.cpp
- back_labirint.cpp
- iepuras.dat
- labirint.dat