1. Un labirint dreptunghiular cu m linii si n coloane contine culoare (reprezentate prin 0) si pereti (reprezentati prin -1). Se dau coordonatele initiale ale unui soricel si coordonatele finale in care trebuie sa ajunga. Pe culoare se gasesc bucati de branza pt care se cunoaste greutatea in grame.
a) Sa se genereze toate solutiile., pt fiecare se afiseaza cantitatea consumata
b) Sa se afiseze solutia cea mai „consistenta”
(Soricelul se poate deplasa in 8 directii)
#include<iomanip>
#include<iostream>
#include<fstream>
using namespace std;
int n,m,L[10][10],sol[10][10],nrsol=0,x,y,z,w,dr[10][10],maxi=0;
int dx[]={-1,0,1,0,-1,1,1,-1},dy[]={0,1,0,-1,1,1,-1,-1};
void citire()
{int i,j;
ifstream f("labi");
f>>n>>m>>x>>y>>z>>w;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
f>>L[i][j];
}
void afisare()
{int i,j;
nrsol++;
cout<<"Solutia nr "<<nrsol<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)
cout<<setw(3)<<sol[i][j];
cout<<endl;}
}
void traseu(int i, int j, int pas,int gr)
{int inou,jnou,k,ii,jj;
for(k=0;k<8;k++)
{inou=i+dx[k];
jnou=j+dy[k];
if(inou>=1 && inou<=n && jnou>=1 && jnou<=m)
if(L[inou][jnou]!=-1 && sol[inou][jnou]==0)
{sol[inou][jnou]=pas;
gr=gr+L[inou][jnou];
if(inou==z && jnou==w)
{
afisare();
cout<<gr<<endl<<endl;
if(gr>maxi)
{maxi=gr;
for(ii=1;ii<=n;ii++)
for(jj=1;jj<=m;jj++)
dr[ii][jj]=sol[ii][jj];}
}
traseu(inou,jnou,pas+1,gr);
sol[inou][jnou]=0;
gr=gr-L[inou][jnou];
}
}
}
int main()
{int i,j;
citire();
sol[x][y]=1;
traseu(x,y,2,L[x][y]);
cout<<"Sol totale "<<nrsol<<endl;
cout<<endl<<"Drumul 8im"<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)
cout<<setw(3)<<dr[i][j];
cout<<endl;}
cout<<endl<<maxi;
}
Fişier
5 4
3 3
5 1
0 0 0 0
-1 -1 8 -1
0 10 0 -1
7 -1 25 -1
0 14 0 -1
2. Fiind data o tabla de sah de dimensiunea nxn si un cal în coltul stânga sus al acesteia, se cere sa se afiseze toate posibilitatile de mutare a acestei piese de sah astfel încât sa treaca o singura data prin fiecare patrat al tablei. O solutie va fi afisata ca o matrice nxn în care sunt numerotate sariturile calului. Exemplu, pentru n=5, o solutie este
1 14 9 20 23
10 19 22 15 8
5 2 13 24 21
18 11 4 7 16
3 6 17 12 25
#include<iomanip>
#include<iostream>
#include<fstream>
using namespace std;
int n,L[10][10],sol[10][10],nrsol=0,x,y,z,w,dr[10][10],maxi=0;
int dx[]={-2,-1,1,2,2,1,-1,-2},dy[]={1,2,2,1,-1,-2,-2,-1};
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 inou,jnou,k;
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;
if(pas==n*n)
afisare();
traseu(inou,jnou,pas+1);
sol[inou][jnou]=0;
}
}
}
int main()
{int i,j;
ifstream f("labi");
f>>n;
sol[1][1]=1;
traseu(1,1,2);
cout<<"Sol totale "<<nrsol<<endl;
}
Din fisier se citeste doar n.
