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


Hercule trebuie sa strabata un labirint cu capcane reprezentat de o matrice nXn. Pentru fiecare celula a labirintului, se cunoaste timpul in minute dupa care celula respectiva devine capcana. Dupa ce o celula devine capcana, Hercule moare daca intra in acea celula.
Hercule porneste din coltul stanga-sus al labirintului si trebuie sa ajunga in coltul dreapta jos. El are nevoie de un minut ca sa treaca dintr-o celula intr-una vecina si se poate deplasa in sus, in jos, spre stanga sau spre dreapta.
Sa se afiseze timpul minim in care poate Hercule sa strabata labirintul, numarul de drumuri de timp minim, precum si toate drumurile minime pe care le poate urma Hercule prin labirint de la intrare la iesire, astfel incat Hercule sa nu moara. Drumurile vor fi afisate ca matrici in care sunt indicati pasii lui Hercule.
Exemplu:
hercule.in
6 6
3 4 5 6 7 8
3 1 1 1 1 9
5 6 7 12 11 10
1 7 1 13 1 1
1 8 1 14 15 16
1 9 10 11 12 17
hercule.out
11 4
1 0 0 0 0 0
2 0 0 0 0 0
3 4 5 6 0 0
0 0 0 7 0 0
0 0 0 8 9 10
0 0 0 0 0 11

1 0 0 0 0 0
2 0 0 0 0 0
3 4 5 6 0 0
0 0 0 7 0 0
0 0 0 8 9 0
0 0 0 0 10 11

1 0 0 0 0 0
2 0 0 0 0 0
3 4 5 6 0 0
0 0 0 7 0 0
0 0 0 8 0 0
0 0 0 9 10 11

1 0 0 0 0 0
2 0 0 0 0 0
3 4 0 0 0 0
0 5 0 0 0 0
0 6 0 0 0 0
0 7 8 9 10 11



#include <fstream>
using namespace std;
ifstream is("hercule.in");
ofstream os("hercule.out");
const int di[]={-1,0,1,0};
const int dj[]={0,1,0,-1};
int a[100][100], x[100][100], m,n,pmin=10000,nr=0;

void citire()
{
    is>>m>>n;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            is>>a[i][j];
}

void afis(int x[100][100])
{
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
            os<<x[i][j]<<" ";
        os<<endl;
    }
    os<<endl;
}

void alege(int pas)//alege minimul si numarul de drumuri de lungime minima
{
    if(pas<pmin) { pmin=pas; nr=1;}
    else if(pas==pmin) nr++;
}

void back(int i, int j, int pas)
{
    x[i][j]=pas;
    if(i==m && j==n) alege(pas);
    else
    for(int d=0;d<4;d++)
    {
        int inou=i+di[d];
        int jnou=j+dj[d];
        if(pas<a[inou][jnou] && x[inou][jnou]==0 && pas<pmin) //inca nu e capcana, e pozitie noua si nu s-a depasit nr min de pasi
                back(inou,jnou,pas+1);
    }
    x[i][j]=0;
}

void backmin(int i, int j, int pas) //face doar drumurile de lungime minima
{
    x[i][j]=pas;
    if(i==m && j==n && pas==pmin) afis(x);
    else
    for(int d=0;d<4;d++)
    {
        int inou=i+di[d];
        int jnou=j+dj[d];
        if(pas<a[inou][jnou] && x[inou][jnou]==0 && pas<pmin)
                backmin(inou,jnou,pas+1);
    }
    x[i][j]=0;
}

int main()
{
    citire();
    back(1,1,1);
    os<<pmin<<" "<<nr<<endl;
    backmin(1,1,1);
    is.close();
    os.close();
    return 0;
}


sau

#include <fstream>
using namespace std;
ifstream is("hercule.in");
ofstream os("hercule.out");
const int di[]={-1,0,1,0};
const int dj[]={0,1,0,-1};
int a[100][100], x[100][100], m,n,pmin=10000,nr=0;

void citire()
{
    is>>m>>n;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            is>>a[i][j];
}

void afis(int x[100][100])
{
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
            os<<x[i][j]<<" ";
        os<<endl;
    }
    os<<endl;
}

void alege(int pas)
{
    if(pas<pmin) { pmin=pas; nr=1;}
    else if(pas==pmin) nr++;
}

void creste()
{
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            a[i][j]++;
}

void scade()
{
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            a[i][j]--;
}

void back(int i, int j, int pas)
{
    scade();
    x[i][j]=pas;
    if(i==m && j==n) alege(pas);
    else
    for(int d=0;d<4;d++)
    {
        int inou=i+di[d];
        int jnou=j+dj[d];
        if(a[inou][jnou]>0 && x[inou][jnou]==0 && pas<pmin)
            {
                back(inou,jnou,pas+1);
            }
    }
    x[i][j]=0;
    creste();
}

void backmin(int i, int j, int pas) //face doar drumurile de lungime minima
{
    scade();
    x[i][j]=pas;
    if(i==m && j==n && pas==pmin) afis(x);
    else
    for(int d=0;d<4;d++)
    {
        int inou=i+di[d];
        int jnou=j+dj[d];
        if(a[inou][jnou]>0 && x[inou][jnou]==0 && pas<pmin)
            {
                backmin(inou,jnou,pas+1);
            }
    }
    x[i][j]=0;
    creste();
}

int main()
{
    citire();
    back(1,1,1);
    os<<pmin<<" "<<nr<<endl;
    backmin(1,1,1);
    is.close();
    os.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