Probleme Rezolvate

Problema capcanelor . Un teren este împărţit în mai multe zone. 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 un pătrat de teren. Anumite pătrate conţin diverse capcane ascunse. O persoană se găseşte în pătratul cu coordonatele x (numărul liniei) şi y1 (numărul coloanei) şi trebuie să ajungă în pătratul cu coordonatele xX2 şi y2 deplasându-se ortogonal şi fără să calce în pătratele cu capcane. Datele se citesc dintr-un fişier text, astfel: de pe primul rând, n, m şi coordonatele pătratului de pornire şi ale pătratului destinație, iar de pe următoarele rânduri — perechile de coordonate ale pătratelor cu capcane. Să se găsească traseele pe care trebuie să le urmeze persoana respectivă. Indicaţie . Construirea soluţiei traseului are următoarele caracteristici:
O soluţie este formată din coordonatele zonelor prin care trece persoana.
Fiecare soluție are un număr variabil de elemente. Primul element al soluției conține coordonatele pătratului din care pleacă persoana, iar ultimul element al soluției conţine coordonatele pătratului în care trebuie să ajungă.
Persoana se poate deplasa în 4 direcţii (corespunzătoare celor 4 pătrate aflate pe diagonala 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 persoana.
Condiţia de continuare a construirii soluției este ca pătratul în care a ajuns persoana să nu conţină capcane.

# include < iostream >
# include < fstream >
const int MAX = 100 ;
int teren[MAX][MAX];
int n = 5 , m = 5 ;
int startX = 0 , startY = 0 ;
int endX = 4 , endY = 4 ;
int dx[] = { 0 , 0 , 1 , -1 };
int dy [] = { 1 , -1 , 0 , 0 };
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;
}
void cautaTraseu ( int traseu[][ 2 ], int idx , int x, int y) {
if (x == endX && y == endY ) {
afisareTraseu (traseu, idx );
return ;
}
if (! esteInTeren (x, y) || teren[x][y] == 1 ) {
return ;
}
teren[x][y] = 1 ;
traseu[ idx ][ 0 ] = x;
traseu[ idx ][ 1 ] = y;
for ( int i = 0 ; i < 4 ; ++i) {
int newX = x + dx[i];
int newY = y + dy [i];
cautaTraseu (traseu, idx + 1 , newX , newY );
}
teren[x][y] = 0 ;
}
int main () {
for ( int i = 0 ; i < n; ++i) {
for ( int j = 0 ; j < m; ++j) {
teren[i][j] = 0 ;
}
}
teren[ 2 ][ 2 ] = 1 ;
teren[ 3 ][ 2 ] = 1 ;
teren[ 1 ][ 3 ] = 1 ;
teren[ 3 ][ 3 ] = 1 ;
teren[ 4 ][ 3 ] = 1 ;
int traseu[MAX * MAX][ 2 ];
cautaTraseu (traseu, 0 , startX , startY );
return 0 ;
}

Acest cod definește o matrice de dimensiune 5x5, cu capcane predefinite. Funcția cautaTraseu explorează recursiv toate direcțiile posibile în care se poate deplasa persoana și afișează traseul când ajunge la destinație.