Probleme Rezolvate

Problema bilei. Un teren este împărţit în mai multe zone, fiecare zonă având o înălțime h. Pentru simplificare, vom considera fiecare zonă ca fiind un pătrat cu aceeaşi dimensiune. Terenul poate fi reprezentat sub forma unei matrice cu n linii şi m coloane, fiecare element al matricei reprezentând înălțimea unei zone de teren. O bilă se găseşte într-o zonă cu coordonatele x (numărul liniei) şi y (numărul coloanei). Ea se poate rostogoli numai către o zonă care are înălțimea mai mică decât cea a zonei în care se găseşte . Să se genereze toate posibilitățile de rostogolire a bilei — până la marginea terenului. indicație. Construirea soluției traseului are următoarele caracteristici;
O soluţie este formată din coordonatele zonelor prin care se rostogoleşte bila.
Fiecare soluţie are un număr variabil de elemente. Primul element al soluției conține coordonatele zonei de plecare a bilei, iar ultimul element al soluţiei conţine coordonatele unei zone de la marginea terenului.
Bila se poate rostogoli în 8 direcţii (corespunzătoare celor 8 pătrate adiacente pătratului în care se găseşte ), fiecare direcție de deplasare corespunzând unei constante de deplasare care se adaugă la coordonata x, respectiv y, a pătratului în care se găseşte bila.
Condiţia de continuare a construirii soluţiei este ca pătratul în care a ajuns bila să aibă înălțimea mai mică decât a pătratului anterior

# include < iostream >
const int MAX = 100 ;
int teren[MAX][MAX];
int n = 4 , m = 4 ;
int startX = 1 , startY = 1 ;
int dx[] = { -1 , -1 , -1 , 0 , 0 , 1 , 1 , 1 };
int dy [] = { -1 , 0 , 1 , -1 , 1 , -1 , 0 , 1 };
void afisareTraseu ( int traseu[][ 2 ], int idx ) {
for ( int i = 0 ; i <= idx ; ++i) {
std :: cout << "(" << traseu[i][ 0 ] << ", " << traseu[i][ 1 ] << ") " ;
}
std :: cout << std :: endl ;
}
bool esteInTeren ( int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m;
}
bool esteMargine ( int x, int y) {
return x == 0 || x == n - 1 || y == 0 || y == m - 1 ;
}
void cautaTraseu ( int traseu[][ 2 ], int idx , int x, int y) {
if (! esteInTeren (x, y)) {
return ;
}
traseu[ idx ][ 0 ] = x;
traseu[ idx ][ 1 ] = y;
if ( esteMargine (x, y) && idx != 0 ) {
afisareTraseu (traseu, idx );
return ;
}
for ( int i = 0 ; i < 8 ; ++i) {
int newX = x + dx[i];
int newY = y + dy [i];
if ( esteInTeren ( newX , newY ) && teren[ newX ][ newY ] < teren[x][y]) {
cautaTraseu (traseu, idx + 1 , newX , newY );
}
}
}
int main () {
teren[ 0 ][ 0 ] = 3 ; teren[ 0 ][ 1 ] = 1 ; teren[ 0 ][ 2 ] = 4 ; teren[ 0 ][ 3 ] = 1 ;
teren[ 1 ][ 0 ] = 1 ; teren[ 1 ][ 1 ] = 5 ; teren[ 1 ][ 2 ] = 1 ; teren[ 1 ][ 3 ] = 2 ;
teren[ 2 ][ 0 ] = 2 ; teren[ 2 ][ 1 ] = 2 ; teren[ 2 ][ 2 ] = 1 ; teren[ 2 ][ 3 ] = 3 ;
teren[ 3 ][ 0 ] = 3 ; teren[ 3 ][ 1 ] = 1 ; teren[ 3 ][ 2 ] = 2 ; teren[ 3 ][ 3 ] = 1 ;
int traseu[MAX * MAX][ 2 ];
cautaTraseu (traseu, 0 , startX , startY );
return 0 ;
}