행렬의 두 셀 사이에 경로가 있는지 확인하는 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