# include < iostream >
# include < queue >
# include < utility >
using namespace std ;
struct Position {
int x, y, step;
};
int dx[] = { -2 , -1 , 1 , 2 , 2 , 1 , -1 , -2 };
int dy [] = { 1 , 2 , 2 , 1 , -1 , -2 , -2 , -1 };
bool valid ( int x, int y, int n) {
return x >= 0 && x < n && y >= 0 && y < n;
}
int minPathLengthBFS ( int n, int x1, int y1, int x2, int y2) {
queue < Position > q;
q. push ({x1, y1, 0 });
while (! q. empty ()) {
Position current = q. front ();
q. pop ();
if ( current.x == x2 && current.y == y2) {
return current.step ;
}
for ( int i = 0 ; i < 8 ; i++) {
int newX = current.x + dx[i];
int newY = current.y + dy [i];
if ( valid ( newX , newY , n)) {
q. push ({ newX , newY , current.step + 1 });
}
}
}
return -1 ;
}
int main () {
int n, x1, y1, x2, y2;
cin >> n >> x1 >> y1 >> x2 >> y2;
int result = minPathLengthBFS (n, x1, y1, x2, y2);
cout << "Minimul folosind BFS: " << result << endl ;
return 0 ;
}
Pentru a rula programul, trebuie să introduci 5 valori separate prin spații sau pe linii diferite:
Coordonatele x și y trebuie să fie între 0 și n-1.
Exemplu de date de intrare:
8
1 3
6 2
O altă soluție eficientă pentru această problemă este utilizarea algoritmului bidirecțional de căutare în lățime ( Bidirectional Breadth-First Search - Bi-BFS). În acest algoritm, căutarea se efectuează în același timp atât de la sursă, cât și de la destinație, întâlnindu-se la mijloc. Acest algoritm este mai rapid decât BFS în unele cazuri, deoarece reduce spațiul de căutare.
Iată implementarea Bi-BFS:
# include < iostream >
# include < queue >
# include < utility >
# include < map >
using namespace std ;
struct Position {
int x, y, step;
};
int dx[] = { -2 , -1 , 1 , 2 , 2 , 1 , -1 , -2 };
int dy [] = { 1 , 2 , 2 , 1 , -1 , -2 , -2 , -1 };
bool valid ( int x, int y, int n) {
return x >= 0 && x < n && y >= 0 && y < n;
}
int minPathLengthBiBFS ( int n, int x1, int y1, int x2, int y2) {
queue < Position > q1, q2;
map <pair< int , int >, int > visited1, visited2;
q1. push ({x1, y1, 0 });
q2. push ({x2, y2, 0 });
visited1[{x1, y1}] = 0 ;
visited2[{x2, y2}] = 0 ;
while (!q1. empty () || !q2. empty ()) {
if (!q1. empty ()) {
Position current = q1. front ();
q1. pop ();
if (visited2. count ({ current.x , current.y }) > 0 ) {
return current.step + visited2[{ current.x , current.y }];
}
for ( int i = 0 ; i < 8 ; i++) {
int newX = current.x + dx[i];
int newY = current.y + dy [i];
if ( valid ( newX , newY , n) && visited1. count ({ newX , newY }) == 0 ) {
q1. push ({ newX , newY , current.step + 1 });
visited1[{ newX , newY }] = current.step + 1 ;
}
}
}
if (!q2. empty ()) {
Position current = q2. front ();
q2. pop ();
if (visited1. count ({ current.x , current.y }) > 0 ) {
return current.step + visited1[{ current.x , current.y }];
}
for ( int i = 0 ; i < 8 ; i++) {
int newX = current.x + dx[i];
int newY = current.y + dy [i];
if ( valid ( newX , newY , n) && visited2. count ({ newX , newY }) == 0 ) {
q2. push ({ newX , newY , current.step + 1 });
visited2[{ newX , newY }] = current.step + 1 ;
}
}
}
}
return -1 ;
}
int main () {
int n, x1, y1, x2, y2;
cin >> n >> x1 >> y1 >> x2 >> y2;
int result = minPathLengthBiBFS (n, x1, y1, x2, y2);
cout << "Minimul folosind Bi-BFS: " << result << endl ;
return 0 ;
}