Probleme de informatica - enunturi si rezolvari

O tabla de sah se citeste ca o matrice n*n in care pozitiile libere au valoarea 0, iar piesele sunt marcate prin valoarea 1.
Sa se determine drumul pe care poate ajunge un pion de pe prima linie pe ultima linie luand un numar maxim de piese. Pe prima linie nu sunt piese si pionul poate porni din orice pozitie de pe prima linie
Pozitia initiala a pionului se considera libera.
Pionul aflat in pozitia i,j se poate deplasa astfel:
- in pozitia i+1,j daca e libera
- in pozitia i+1, j-1 daca e piesa in aceasta pozitie
- in pozitia i+1, j+1 daca e piesa in aceasta pozitie

Exemplu:
5
0 0 0 0 0
0 1 0 1 0
0 1 1 1 1
0 0 0 1 1
0 1 0 1 1

Drumul optim este:
1 1
2 2
3 3
4 4
5 5
Pe acest drum pionul ia 4 piese.

#include<fstream>
using namespace std;
ifstream fin("pion.in");
ofstream fout("pion.out");
int n,i,j, a[50][50], c[50][50];
void citire()
{ int i,j;
  fin>>n;
  is=1;
  for(i=1;i<=n;i++)
	for(j=1;j<=n;j++) fin>>a[i][j];
}
void pd()
{ int i,j;
  for(i=2;i<=n;i++)
	  for(j=1;j<=n;j++)
		 if(a[i][j]==0) c[i][j]=c[i-1][j];
		  else if(c[i-1][j-1]>c[i-1][j+1]) c[i][j]=c[i-1][j-1]+1;
			   else c[i][j]=c[i-1][j+1]+1;
		
}
void drum(int i, int j)
{
   if(i==1) fout<<i<<" "<<j<<endl;
   else { if(a[i][j]==0) drum(i-1,j);
		  else if(c[i-1][j-1]+1==c[i][j])
					 drum(i-1,j-1);
			   else drum(i-1,j+1);
		  fout<<i<<" "<<j<<endl;
        }
}
void afis()
{
  int max=0,jm;
  for(j=1;j<=n;j++) if(c[n][j]>max) { max=c[n][j]; jm=j; }
  fout<<max-1<<endl;
  drum(n,jm);
}

int  main()
{ citire();
  pd();
  afis();
  fin.close();
  fout.close();
  return 0;
}

19 apr 2024

Site-ul conține 884 de probleme rezolvate