ম্যাট্রিক্সে দুটি কোষের মধ্যে একটি পথ আছে কিনা তা খুঁজে বের করতে C++ প্রোগ্রাম

এই নিবন্ধে, আমরা একটি প্রদত্ত ম্যাট্রিক্সে দুটি কোষের মধ্যে একটি পথ আছে কিনা তা খুঁজে বের করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব৷

ধরা যাক আমাদের সম্ভাব্য মান 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