Probleme de informatică
Clasa a IX-a
Elementele de bază C++ (46)
Subprograme predefinite (1)
Fişiere text (2)
Algoritmi elementari (111)
Tablouri unidimensionale (83)
Tablouri bidimensionale (64)
Probleme diverse (13)
Clasa a X-a
Subprograme (funcții) (87)
Şiruri de caractere (50)
Tipul înregistrare (26)
Recursivitate (57)
Alocarea dinamică a memoriei (2)
Liste înlănţuite (25)
Algoritmul lui Lee (1)
Clasa a XI-a
Metoda "Divide et impera" (12)
Metoda Backtracking (86)
Metoda Greedy (6)
Programare dinamică (18)
Grafuri neorientate (40)
Grafuri orientate (38)
Arbori (33)
Clasa a XII-a
Elemente de bază C# (32)
POO în C# (14)
Programare vizuală în C# (19)
Examen de bacalaureat
Competențe digitale
Examen de atestat
Admitere UBB (18)
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;
}

29 mar 2024
Site-ul conține 884 de probleme rezolvate
Copyright © 2009-2018 Muresan Vasile Ciprian