Pe o tabla de sah n x n 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 cu numar minim de pasi astfel incat calul 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.
#include<iomanip>Fişier
#include<iostream>
#include<fstream>
using namespace std;
int n,m,L[10][10],sol[10][10],nrsol=0,x,y,z,w,drmin[10][10],mi, px[100],py[100],iz,jz;
int dx[]={-2,-1,2,1,2,1,-1,-2},dy[]={1,2,1,2,-1,-2,-2,-1};
void citire()
{int i,j;
ifstream f("sah");
f>>n>>m;
for(i=1;i<=m;i++)
f>>px[i]>>py[i];
f>>iz>>jz;
}
void afisare()
{int i,j;
nrsol++;
cout<<"Solutia nr "<<nrsol<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
cout<<setw(3)<<sol[i][j];
cout<<endl;}
cout<<endl;
}
void traseu(int i, int j, int pas, int s)
{int inou,jnou,k,ii,jj,snou;
for(k=0;k<8;k++)
{inou=i+dx[k];
jnou=j+dy[k];
if(inou>=1 && inou<=n && jnou>=1 && jnou<=n)
if(sol[inou][jnou]==0)
{sol[inou][jnou]=pas;
snou=s+L[inou][jnou];
if(snou==m)
{//afisare();
if(pas<mi)
{mi=pas;
for(ii=1;ii<=n;ii++)
for(jj=1;jj<=n;jj++)
drmin[ii][jj]=sol[ii][jj];
}
}
if (pas < mi)
traseu(inou,jnou,pas+1,snou);
sol[inou][jnou]=0;
}
}
}
int main()
{int i,j;
citire();
sol[iz][jz]=1;
for(i=1;i<=m;i++)
L[px[i]][py[i]]=1;
mi=n*n;
traseu(iz,jz,2,0);
cout<<"Sol totale "<<nrsol<<endl;
cout<<endl<<"Drumul optim"<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
cout<<setw(3)<<drmin[i][j];
cout<<endl;}
cout<<endl<<mi;
cout<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
cout<<setw(3)<<L[i][j];
cout<<endl;}
cout<<endl;
}
5
6
1 3
3 4
2 2
1 5
5 2
4 1
1 1
