Menu
Probleme Rezolvate
Manual clasa a Xi a |
Tehnici de programare |
Microproiecte |
Pentru a rezolva această problemă cu metoda backtracking , vom utiliza o matrice pentru a reprezenta labirintul. Fiecare element al matricei va fi 0 sau 1, unde 0 reprezintă o cărămidă sau un perete, iar 1 reprezintă un drum sau un spațiu liber. De asemenea, vom utiliza o matrice vizitat pentru a urmări pozițiile vizitate și pentru a evita ciclurile infinite în timpul căutării.
Pasul de bază al metodei backtracking este să începem cu poziția de start (x, y) și să încercăm să ne deplasăm în sus, în jos, la stânga sau la dreapta, verificând în fiecare direcție dacă putem ajunge la o poziție validă și nevizitată. Dacă putem ajunge la o astfel de poziție, vom marca poziția ca vizitată și vom adăuga poziția la traseul nostru. Vom continua să ne deplasăm în acest mod până când ajungem la ieșirea din labirint sau nu mai putem avansa în nicio direcție.
Dacă nu putem ajunge la o poziție validă, vom reveni la ultima poziție și vom încerca să ne deplasăm într-o altă direcție. Vom continua această metodă până când găsim o soluție sau până când am încercat toate direcțiile posibile și nu putem găsi o soluție.
Pentru metoda greedy , vom utiliza un algoritm care alege mereu următoarea poziție bazată pe o euristică. În cazul nostru, vom utiliza distanța euclidiană pentru a alege următoarea poziție. Adică vom calcula distanța euclidiană între poziția curentă și fiecare poziție validă nevizitată și vom alege poziția cu cea mai mică distanță euclidiană. Vom continua această metodă până când ajungem la ieșirea din labirint sau până când nu mai există poziții valide nevizitate.
Exemplu de date de intrare:
Dimensiunea labirintului: 5 6 Labirintul: 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 Poziția de start: 1 1
Aceste date de intrare descriu un labirint de 5 rânduri și 6 coloane, cu un drum deschis care începe la poziția (1, 1).
# include < iostream >
# include < cstring >
using namespace std ;
const int N = 100 ;
int maze [N][N], sol[N][N];
// Verifică dacă o celulă poate fi accesată (este liberă și se află în interiorul labirintului)
bool isValid ( int x, int y, int n, int m) {
if (x >= 0 && x < n && y >= 0 && y < m && maze [x][y] == 1 ) {
return true ;
}
return false ;
}
// Găsește un traseu în labirint
bool solveMaze ( int x, int y, int n, int m) {
// Verifică dacă am ajuns la ieșirea din labirint
if (x == n - 1 && y == m - 1 ) {
sol[x][y] = 1 ;
return true ;
}
// Verifică dacă poziția curentă este validă
if ( isValid (x, y, n, m)) {
sol[x][y] = 1 ;
// Verifică dacă se poate ajunge la ieșire din poziția curentă mergând în jos
if ( solveMaze (x + 1 , y, n, m)) {
return true ;
}
// Verifică dacă se poate ajunge la ieșire din poziția curentă mergând la dreapta
if ( solveMaze (x, y + 1 , n, m)) {
return true ;
}
// Dacă nu se poate ajunge la ieșire din poziția curentă, marchează poziția ca nevizitată
sol[x][y] = 0 ;
return false ;
}
return false ;
}
int main () {
int n, m;
// Citirea dimensiunilor labirintului
cout << " Introduceti numarul de linii: " ;
cin >> n;
cout << " Introduceti numarul de coloane: " ;
cin >> m;
// Citirea labirintului
cout << " Introduceti matricea labirintului:" << endl ;
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < m; j++) {
cin >> maze [i][j];
}
}
// Inițializarea matricei sol cu valoarea 0
memset (sol, 0 , sizeof (sol));
// Găsirea unui traseu în labirint
if ( solveMaze ( 0 , 0 , n, m)) {
cout << "Un traseu gasit :" << endl ;
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < m; j++) {
cout << sol[i][j] << " " ;
}
cout << endl ;
}
} else {
cout << "Nu exista niciun traseu gasit !" << endl ;
}
return 0 ;
}
I ată un exemplu de labirint și o posibilă soluție de ieșire din acesta:
5 6
1 1
0 0 0 0 0 0
1 1 1 1 0 1
0 0 0 1 0 0
0 1 1 1 1 0
0 0 0 0 0 0
În acest exemplu, dimensiunile labirintului sunt 5x6, iar poziția de start este (1,1). Drumul deschis este reprezentat de valorile 1 în matrice, iar obstacolele (pereții) de valorile 0.
O posibilă soluție de ieșire din acest labirint ar fi:
x x x x x x
1 1 1 1 x 1
0 0 0 1 x x
0 1 1 1 1 x
0 0 0 0 0 x
Iată o implementare în C++ a algoritmului Greedy pentru găsirea unui traseu prin labirint.
# include < iostream >
# include < cstring >
# include < cmath >
# define MAX_N 100
# define MAX_M 100
using namespace std ;
int n, m, startX , startY , endX , endY ;
char maze [MAX_N][MAX_M];
bool visited [MAX_N][MAX_M];
// Direcțiile de deplasare
int dx[] = { 1 , 0 , -1 , 0 };
int dy [] = { 0 , 1 , 0 , -1 };
// Verifică dacă o celulă este validă (în interiorul labirintului și nevizitată)
bool isValid ( int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m && maze [x][y] == '.' && ! visited [x][y];
}
// Algoritmul Greedy
bool greedy ( int x, int y) {
// Dacă am ajuns la destinație, am găsit traseul
if (x == endX && y == endY ) {
return true ;
}
visited [x][y] = true ;
int minDist = 1e9 , nextX = -1 , nextY = -1 ;
// Căutăm celula vecină cu distanța minimă la destinație
for ( int i = 0 ; i < 4 ; i++) {
int nx = x + dx[i], ny = y + dy [i];
if ( isValid ( nx , ny )) {
double dist = sqrt (( nx - endX ) * ( nx - endX ) + ( ny - endY ) * ( ny - endY )); if ( dist < minDist ) {
minDist = dist ;
nextX = nx ;
nextY = ny ;
}
}
}
// Dacă am găsit o celulă vecină validă, continuăm căutarea
if ( nextX != -1 && nextY != -1 ) {
if ( greedy ( nextX , nextY )) {
return true ;
}
}
// Dacă nu am găsit o celulă vecină validă, ne întoarcem înapoi
visited [x][y] = false ;
return false ;
}
int main () {
// Citim dimensiunile labirintului și coordonatele de start și sfârșit
cin >> n >> m >> startX >> startY >> endX >> endY ;
// Citim harta labirintului
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < m; j++) {
cin >> maze [i][j];
}
}
// Inițializăm matricea visited cu false
memset ( visited , false , sizeof ( visited ));
// Aplicăm algoritmul Greedy pentru a găsi traseul
if ( greedy ( startX , startY )) {
cout << "Traseul a fost gasit \n" ;
} else {
cout << "Nu exista traseu\n" ;
}
return 0 ;
}
# include < cstring >
using namespace std ;
const int N = 100 ;
int maze [N][N], sol[N][N];
// Verifică dacă o celulă poate fi accesată (este liberă și se află în interiorul labirintului)
bool isValid ( int x, int y, int n, int m) {
if (x >= 0 && x < n && y >= 0 && y < m && maze [x][y] == 1 ) {
return true ;
}
return false ;
}
// Găsește un traseu în labirint
bool solveMaze ( int x, int y, int n, int m) {
// Verifică dacă am ajuns la ieșirea din labirint
if (x == n - 1 && y == m - 1 ) {
sol[x][y] = 1 ;
return true ;
}
// Verifică dacă poziția curentă este validă
if ( isValid (x, y, n, m)) {
sol[x][y] = 1 ;
// Verifică dacă se poate ajunge la ieșire din poziția curentă mergând în jos
if ( solveMaze (x + 1 , y, n, m)) {
return true ;
}
// Verifică dacă se poate ajunge la ieșire din poziția curentă mergând la dreapta
if ( solveMaze (x, y + 1 , n, m)) {
return true ;
}
// Dacă nu se poate ajunge la ieșire din poziția curentă, marchează poziția ca nevizitată
sol[x][y] = 0 ;
return false ;
}
return false ;
}
int main () {
int n, m;
// Citirea dimensiunilor labirintului
cout << " Introduceti numarul de linii: " ;
cin >> n;
cout << " Introduceti numarul de coloane: " ;
cin >> m;
// Citirea labirintului
cout << " Introduceti matricea labirintului:" << endl ;
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < m; j++) {
cin >> maze [i][j];
}
}
// Inițializarea matricei sol cu valoarea 0
memset (sol, 0 , sizeof (sol));
// Găsirea unui traseu în labirint
if ( solveMaze ( 0 , 0 , n, m)) {
cout << "Un traseu gasit :" << endl ;
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < m; j++) {
cout << sol[i][j] << " " ;
}
cout << endl ;
}
} else {
cout << "Nu exista niciun traseu gasit !" << endl ;
}
return 0 ;
}
I ată un exemplu de labirint și o posibilă soluție de ieșire din acesta:
5 6
1 1
0 0 0 0 0 0
1 1 1 1 0 1
0 0 0 1 0 0
0 1 1 1 1 0
0 0 0 0 0 0
În acest exemplu, dimensiunile labirintului sunt 5x6, iar poziția de start este (1,1). Drumul deschis este reprezentat de valorile 1 în matrice, iar obstacolele (pereții) de valorile 0.
O posibilă soluție de ieșire din acest labirint ar fi:
x x x x x x
1 1 1 1 x 1
0 0 0 1 x x
0 1 1 1 1 x
0 0 0 0 0 x
Iată o implementare în C++ a algoritmului Greedy pentru găsirea unui traseu prin labirint.
# include < iostream >
# include < cstring >
# include < cmath >
# define MAX_N 100
# define MAX_M 100
using namespace std ;
int n, m, startX , startY , endX , endY ;
char maze [MAX_N][MAX_M];
bool visited [MAX_N][MAX_M];
// Direcțiile de deplasare
int dx[] = { 1 , 0 , -1 , 0 };
int dy [] = { 0 , 1 , 0 , -1 };
// Verifică dacă o celulă este validă (în interiorul labirintului și nevizitată)
bool isValid ( int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m && maze [x][y] == '.' && ! visited [x][y];
}
// Algoritmul Greedy
bool greedy ( int x, int y) {
// Dacă am ajuns la destinație, am găsit traseul
if (x == endX && y == endY ) {
return true ;
}
visited [x][y] = true ;
int minDist = 1e9 , nextX = -1 , nextY = -1 ;
// Căutăm celula vecină cu distanța minimă la destinație
for ( int i = 0 ; i < 4 ; i++) {
int nx = x + dx[i], ny = y + dy [i];
if ( isValid ( nx , ny )) {
double dist = sqrt (( nx - endX ) * ( nx - endX ) + ( ny - endY ) * ( ny - endY )); if ( dist < minDist ) {
minDist = dist ;
nextX = nx ;
nextY = ny ;
}
}
}
// Dacă am găsit o celulă vecină validă, continuăm căutarea
if ( nextX != -1 && nextY != -1 ) {
if ( greedy ( nextX , nextY )) {
return true ;
}
}
// Dacă nu am găsit o celulă vecină validă, ne întoarcem înapoi
visited [x][y] = false ;
return false ;
}
int main () {
// Citim dimensiunile labirintului și coordonatele de start și sfârșit
cin >> n >> m >> startX >> startY >> endX >> endY ;
// Citim harta labirintului
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < m; j++) {
cin >> maze [i][j];
}
}
// Inițializăm matricea visited cu false
memset ( visited , false , sizeof ( visited ));
// Aplicăm algoritmul Greedy pentru a găsi traseul
if ( greedy ( startX , startY )) {
cout << "Traseul a fost gasit \n" ;
} else {
cout << "Nu exista traseu\n" ;
}
return 0 ;
}