इस लेख में, हम यह पता लगाने के लिए एक कार्यक्रम पर चर्चा करेंगे कि किसी दिए गए मैट्रिक्स में दो कोशिकाओं के बीच पथ मौजूद है या नहीं।
मान लीजिए कि हमें 0, 1, 2 और 3 संभावित मानों वाला एक वर्ग मैट्रिक्स दिया गया है। यहाँ,
- 0 का अर्थ है खाली दीवार
- 1 का अर्थ है स्रोत
- 2 का अर्थ है गंतव्य
- 3 का अर्थ है खाली सेल
मैट्रिक्स में केवल एक स्रोत और गंतव्य हो सकता है। कार्यक्रम यह देखने के लिए है कि क्या दिए गए मैट्रिक्स में स्रोत से गंतव्य तक सभी चार संभावित दिशाओं में आगे बढ़ने का कोई संभावित मार्ग है, लेकिन तिरछे नहीं।
उदाहरण
#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;
} आउटपुट
Not Possible
