11/9 - Prob. 4 si 7

4. 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, iar intr-o pozitie (i1,j1) un rege. Sa se determine toate traseele pe care calul poate sa mearga din pozitia initiala pana in cea a regelui si sa se intoaca de unde a plecat fara a trece de 2 ori prin aceeasi pozitie si mergand doar pe pozitii libere. Se citesc mai intai n si m, iar apoi m perechi reprezentand coordonatele pieselor. Ultimele se citesc coordonatele calului si ale regelui. Traseele se vor marca intr-o matrice si se for afisa si coordonatele prin care trece calul.

#include<iomanip>
#include<iostream>
#include<fstream>
using namespace std;
int n,m,L[10][10],sol[10][10],nrsol=0,calx,caly,regex,regey,ok=0;
int dx[]={-2,-1,2,1,2,1,-1,-2},dy[]={1,2,1,2,-1,-2,-2,-1};

void citire()
{int i,a,b;
ifstream f("sah");
f>>n>>m;
for(i=1;i<=m;i++)
    {f>>a>>b;
    L[a][b]=-1;}
f>>calx>>caly;
f>>regex>>regey;
}

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)<<L[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(L[inou][jnou]==1 && L[regex][regey]>0)
        afisare();
    else
        if(L[inou][jnou]==0 && L[inou][jnou]!=-1)
            {L[inou][jnou]=pas;
            traseu(inou,jnou,pas+1);
            L[inou][jnou]=0;
            }
}
}

int main()
{int i,j;
citire();
L[calx][caly]=1;
traseu(calx,caly,2);
cout<<"Sol totale "<<nrsol<<endl<<endl;
}

Fisier

5
6
1 3
3 4
2 2
1 5
5 2
4 1
1 1
4 5

7. Pe o tabla de sah nXn sunt plasate marcate prin valoarea 1, iar prin valoarea 0 sunt marcate pozitiile libere. Intr-o pozitie j0 de pe prima linie se afla un pion. Determinati toate traseele pe care poate ajunge pionul pana pe ultima linie. Traseele vor fi afisate atat in matrice cat si ca sir de pozitii.
Exemplu:
pentru datele
5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
3
exista 3 solutii marcate in matrice:
0 0 0 0 0
0 0 1 0 0
0 0 2 0 0
0 1 3 1 0
0 0 4 0 0
sau
0 0 0 0 0
0 0 1 0 0
0 0 2 0 0
0 3 0 1 0
0 4 0 0 0
sau
0 0 0 0 0
0 0 1 0 0
0 0 2 0 0
0 1 0 3 0
0 0 0 4 0

#include<iomanip>
#include<iostream>
#include<fstream>
using namespace std;
int n,m,L[10][10],sol[10][10],nrsol=0,start;
int dx[]={1,1,1},dy[]={0,-1,1};

void citire()
{int i,j;
ifstream f("sah");
f>>n;
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        f>>L[i][j];
f>>start;
}

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)<<L[i][j];
cout<<endl;}
cout<<endl;
}

void traseu(int i, int j, int pas)
{int inou,jnou,k;
for(k=0;k<3;k++)
{inou=i+1;
jnou=j+dy[k];
if(inou>=1 && inou<=n && jnou>=1 && jnou<=n)
    if(jnou==j && L[inou][jnou]==0 || jnou!=j && L[inou][jnou]==1)
        {L[inou][jnou]=pas;
        if(inou==n)
            afisare();
   
    traseu(inou,jnou,pas+1);
    L[inou][jnou]=0;}
}
}
   
int main()
{int i,j;
citire();
L[1][start]=1;
traseu(1,start,2);
cout<<"Sol totale "<<nrsol<<endl<<endl;
}

Fisier

5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
3