#include<fstream.h>
fstream f("date.in", ios::in);
fstream g("date.out",ios::out);
int a[100][100],n,io,jo,i1,j1,b[100][3],m;
int min=1000, bsol[100][3], bmat[100][100];
di[8]={-2,-2,-1,1,2,2,1,-1};
dj[8]={-1,1,2,2,1,-1,-2,-2};
int inside(int i,int j)
{ return i>=1 && j>=1 && i<=n && j<=n;
}
void citire()
{ f>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{ f>>a[i][j];
if(a[i][j]==-1) m++;
}
f>>io>>jo;
}
void alege(int k)
{if(k<min)
{ min=k;
int i,j;
for(i=0;i<=min;i++){ bsol[i][1]=b[i][1]; bsol[i][2]=b[i][2];
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
bmat[i][j]=a[i][j];
}
}
void afis()
{ for(int i=1;i<=n;i++)
{ g<<endl;
for(int j=1;j<=n;j++)
g<<bmat[i][j]<<" ";
}
g<<endl;
for(i=0;i<=min; i++)
g<<bsol[i][1]<<","<<bsol[i][2]<<" ";
g<<endl;
}
void back(int i,int j,int k, int l)
{ if(l==m) alege(k-1);
else for(int p=0;p<=7;p++)
{int inou,jnou;
inou=i+di[p];
jnou=j+dj[p];
if(inside(inou,jnou)&& a[inou][jnou]<=0)
{
b[k][1]=inou;
b[k][2]=jnou;
if(a[inou][jnou]==0){ a[inou][jnou]=k+1;
back(inou,jnou,k+1,l);
a[inou][jnou]=0;
}
else{ a[inou][jnou]=k+1;
back(inou,jnou,k+1,l+1);
a[inou][jnou]=-1;
}
}
}
}
void main()
{ citire();
a[io][jo]=1;
b[0][1]=io;
b[0][2]=jo;
back(io,jo,1,0);
afis();
}
vineri, 24 ianuarie 2014
problema rezolvata metoda backtracking
Pe o tabla de sah nXn sunt plasate m piese marcate prin valoarea -1, iar prin valoarea 0 sunt marcate pozitiile libere. Intr-o pozitie (i0,j0) se afla un cal. Sa se determine traseul format din numar minim de pasi pe care calul poate sa manance toate piesele de pe tabla fara a trece de 2 ori prin aceeasi pozitie. Se citesc mai intai n si m, iar apoi m perechi reprezentand coordonatele pieselor. Ultimele se citesc coordonatele calului. Traseul va fi marcat intr-o matrice care se va afisa.
Abonați-vă la:
Postare comentarii (Atom)
Niciun comentariu:
Trimiteți un comentariu