Probleme de informatică
  Clasa a IX-a
1. Elementele de bază ale limbajului C++ (instructiunile limbajului) (46)
2. Subprograme predefinite (1)
3. Tablouri (145)
4. Fişiere text (2)
5. Algoritmi elementari (104)
6. Probleme diverse (12)
  Clasa a X-a
1. Subprograme definite de utilizator (87)
2. Şiruri de caractere (42)
3. Înregistrări (26)
4. Recursivitate (57)
5. Combinatorica (0)
6. Alocarea dinamică a memoriei (2)
7. Liste înlănţuite (25)
8. Algoritmul lui Lee (1)
  Clasa a XI-a

1. Metoda "Divide et impera" (12)
2. Metoda Backtracking (85)
3. Metoda Greedy (6)
4. Programare dinamică (18)
5. Grafuri neorientate (37)
6. Grafuri orientate (38)
7. Arbori (33)

  Clasa a XII-a
1. Elemente de baza C# (32)
2. POO in C# (13)
3. C# - Windows Form Application (24)
4. Admitere UBB (12)

   Home Backtracking Bacalaureat 2016   |   Variante bacalaureat 2009   |   Atestat  |   Olimpiada       
Noutăţi
Subiecte admitere la Facultatea de informatica UBB Cluj-Napoca
Subiecte bacalaureat 2010-2017
Bacalaureat 2017 - competenţe digitale
C# - Windows Form Application - exemple
Modele de proiecte de atestat
Bacalaureat 2017
Subiecte si rezolvări 2010-2017
Rezolvari variante bacalaureat 2009
Competenţe digitale
Examen atestat
Rezumat documentatie
Teme proiect
php.doc
css.doc
exemple_php_si_css.rar
Modele de proiecte de atestat
Subiecte atestat 2014 CNLR
Olimpiada
Clasele V-VI
Clasele VII-VIII
Clasa a IX-a
Clasa a X-a
Clasele XI-XII
Noţiuni teoretice
Metode de sortare
Metoda backtracking


Harta unui oras este codificata ca o matrice nXm in care 0 reprezinta pozitie accesibila (strada) si -1 reprezinta pozitie inaccesibila (clarire, zid).
In pozitia ir,jr se afla Romeo, iar in pozitia ij,jj se afla Julieta. Romeo se poate deplasa pe pozitii cu laloarea 0, alaturate pe linii si coloane cu pozitia curenta, fara sa treaca de doua ori prin aceeasi pozitie.
Determinati si afisati cel mai scurt traseu pe care poate ajunge romeo la Julieta. Solutia se va afisa prin pasi marcari in matrice si ca sir de coordonate prin care trece Romeo.
Toate datele se citesc din fisierul rj.in, iar solutia se afiseaza in fisierul rj.out.
Exemplu:
Pentru datele de intrare:
5 7
-1 -1 0 -1 -1 -1 -1
-1 0 0 0 0 0 0
-1 0 -1 -1 -1 0 -1
-1 0 0 0 0 0 0
-1 -1 -1 -1 -1 -1 -1
2 2
3 6
solutia este:
-1 -1 0 -1 -1 -1 -1
-1 1 2 3 4 5 0
-1 0 -1 -1 -1 6 -1
-1 0 0 0 0 0 0
-1 -1 -1 -1 -1 -1 -1
2,2 2,3 2,4 2,5 2,6 3,6



#include<fstream>
#include<iostream>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
const int di[4]={-1,0,1,0};
const int dj[4]={0,1,0,-1};
int a[10][10], b[10][10],sol[100][3],x[100][3],n,m,pmin=100;
int ir,jr,ij,jj;
void citire()
{
	fin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			fin>>a[i][j];
	fin>>ir>>jr>>ij>>jj;	
}

int inside(int i, int j)
{
	return i>=1 && i<=n && j>=1 && j<=m;
}

void alege(int pas)
{
	if(pas<pmin)
	{
		pmin=pas;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				b[i][j]=a[i][j];
		for(int i=1;i<=pas;i++)
				{ sol[i][1]=x[i][1];
				  sol[i][2]=x[i][2];
				}  
	}
}

void afis()
{
	for (int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			fout<<b[i][j]<<" ";
        fout<<endl;		
	}
	for(int i=1;i<=pmin;i++)
		fout<<sol[i][1]<<","<<sol[i][2]<<"  ";
}

void back(int i,int j, int pas)
{
	int inou, jnou,k;
	if(i==ij && j==jj) alege(pas-1);
	else
		for(k=0;k<=3;k++)
		{
			inou=i+di[k];
			jnou=j+dj[k];
			if(inside(inou,jnou) && a[inou][jnou]==0 )
			{
				a[inou][jnou]=pas;
				x[pas][1]=inou;
				x[pas][2]=jnou;
				back(inou,jnou,pas+1);
				a[inou][jnou]=0;
			}
		}
}

int main()
{
	citire();
	a[ir][jr]=1;
	x[1][1]=ir;
	x[1][2]=jr;
	back(ir,jr,2);
	afis();
	fin.close();
	fout.close();
	return 0;
}


  Clasa a IX-a
1. Elementele de bază ale limbajului C++ (instructiunile limbajului) (46)
2. Subprograme predefinite (1)
3. Tablouri (145)
4. Fişiere text (2)
5. Algoritmi elementari (104)
6. Probleme diverse (12)
  Clasa a X-a
1. Subprograme definite de utilizator (87)
2. Şiruri de caractere (42)
3. Înregistrări (26)
4. Recursivitate (57)
5. Combinatorica (0)
6. Alocarea dinamică a memoriei (2)
7. Liste înlănţuite (25)
8. Algoritmul lui Lee (1)
  Clasa a XI-a

1. Metoda "Divide et impera" (12)
2. Metoda Backtracking (85)
3. Metoda Greedy (6)
4. Programare dinamică (18)
5. Grafuri neorientate (37)
6. Grafuri orientate (38)
7. Arbori (33)

  Clasa a XII-a
1. Elemente de baza C# (32)
2. POO in C# (13)
3. C# - Windows Form Application (24)
4. Admitere UBB (12)

Calculatoare si accesorii second hand
Copyright 2009-2017 Muresan Vasile Ciprian - mcip.ro