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.
Pe prima linie pe coloana js se afla un pion. Sa se determine drumul pe care poate ajunge pionul pe ultima linie luand un numar maxim de piese.
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 3
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 3
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],b[50][50],is,js;
void citire()
{ int i,j;
  fin>>n>>js;
  is=1;
  for(i=1;i<=n;i++)
	for(j=1;j<=n;j++) fin>>a[i][j];
}
void pd()
{ int i,j;
  b[is][js]=1;
  for(i=2;i<=n;i++)
	{
	  for(j=1;j<=n;j++)
		{ if(a[i][j]==0)
		   { if(b[i-1][j]>0) { c[i][j]=c[i-1][j]; b[i][j]=1; }
		   }
		  else if(c[i-1][j-1]>c[i-1][j+1])
		        {
		            if(b[i-1][j-1]>0) {c[i][j]=c[i-1][j-1]+1;b[i][j]=1; }
		            else if(b[i-1][j+1]>0) {c[i][j]=c[i-1][j+1]+1;b[i][j]=1; }
		        }
			   else {
		            if(b[i-1][j+1]>0) {c[i][j]=c[i-1][j+1]+1;b[i][j]=1; }
		            else if(b[i-1][j-1]>0) {c[i][j]=c[i-1][j-1]+1;b[i][j]=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<<endl;
 drum(n,jm);
}

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

21 nov 2024

Site-ul conține 884 de probleme rezolvate