Trong bài viết này, chúng ta sẽ thảo luận về một chương trình để tìm xem liệu có tồn tại một đường dẫn giữa hai ô trong một ma trận nhất định hay không.
Giả sử chúng ta đã được cung cấp một ma trận vuông với các giá trị có thể là 0, 1, 2 và 3. Ở đây,
- 0 nghĩa là Tường trống
- 1 có nghĩa là Nguồn
- 2 có nghĩa là Điểm đến
- 3 có nghĩa là Ô trống
Chỉ có thể có một Nguồn và Đích trong ma trận. Chương trình là để xem liệu có một con đường khả thi nào từ Nguồn đến Đích trong ma trận đã cho di chuyển theo cả bốn hướng khả dĩ nhưng không theo đường chéo hay không.
Ví dụ
#include<bits/stdc++.h>
using namespace std;
//creating a possible graph from given array
class use_graph {
int W;
list <int> *adj;
public :
use_graph( int W ){
this->W = W;
adj = new list<int>[W];
}
void add_side( int source , int dest );
bool search ( int source , int dest);
};
//function to add sides
void use_graph :: add_side ( int source , int dest ){
adj[source].push_back(dest);
adj[dest].push_back(source);
}
//function to perform BFS
bool use_graph :: search(int source, int dest) {
if (source == dest)
return true;
// initializing elements
bool *visited = new bool[W];
for (int i = 0; i < W; i++)
visited[i] = false;
list<int> queue;
//marking elements visited and removing them from queue
visited[source] = true;
queue.push_back(source);
//moving to the adjacent vertices
list<int>::iterator i;
while (!queue.empty()){
source = queue.front();
queue.pop_front();
for(i=adj[source].begin();i!=adj[source].end(); ++i) {
if (*i == dest)
return true;
if (!visited[*i]) {
visited[*i] = true;
queue.push_back(*i);
}
}
}
//if destination is not reached
return false;
}
bool is_okay(int i, int j, int M[][4]) {
if ((i < 0 || i >= 4) || (j < 0 || j >= 4 ) || M[i][j] == 0)
return false;
return true;
}
bool find(int M[][4]) {
int source , dest ;
int W = 4*4+2;
use_graph g(W);
int k = 1 ;
for (int i =0 ; i < 4 ; i++){
for (int j = 0 ; j < 4; j++){
if (M[i][j] != 0){
if ( is_okay ( i , j+1 , M ) )
g.add_side ( k , k+1 );
if ( is_okay ( i , j-1 , M ) )
g.add_side ( k , k-1 );
if (j < 4-1 && is_okay ( i+1 , j , M ) )
g.add_side ( k , k+4 );
if ( i > 0 && is_okay ( i-1 , j , M ) )
g.add_side ( k , k-4 );
}
if( M[i][j] == 1 )
source = k ;
if (M[i][j] == 2)
dest = k;
k++;
}
}
return g.search (source, dest) ;
}
int main(){
int M[4][4] = { { 0 , 3 , 0 , 1 }, { 3 , 0 , 3 , 3 }, { 2 , 3 , 0 , 3 },{ 0 , 0 , 3 , 0 }};
(find(M) == true) ?
cout << "Possible" : cout << "Not Possible" <<endl ;
return 0;
} Đầu ra
Not Possible