Probleme de informatica - enunturi si rezolvari

Probleme de informatică
Clasa a IX-a
Elementele de bază C++ (46)
Subprograme predefinite (1)
Fişiere text (2)
Algoritmi elementari (109)
Tablouri unidimensionale (83)
Tablouri bidimensionale (64)
Probleme diverse (13)
Clasa a X-a
Subprograme (funcții) (87)
Şiruri de caractere (49)
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 (85)
Metoda Greedy (6)
Programare dinamică (18)
Grafuri neorientate (37)
Grafuri orientate (38)
Arbori (33)
Clasa a XII-a
Elemente de bază C# (32)
POO în C# (13)
Programare vizuală în C# (10)
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.
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;
}

17 aug 2018
Site-ul conține 867 de probleme rezolvate
Copyright © 2009-2018 Muresan Vasile Ciprian