একটি গোলকধাঁধা সমস্যা ইঁদুর

এই সমস্যায়, N x N আকারের একটি প্রদত্ত গোলকধাঁধা রয়েছে। উৎস এবং গন্তব্য স্থানটি যথাক্রমে উপরের-বাম কক্ষ এবং নীচে ডান কক্ষ। কিছু কোষ সরানোর জন্য বৈধ এবং কিছু কোষ অবরুদ্ধ। যদি একটি ইঁদুর শুরুর শীর্ষ থেকে গন্তব্য শীর্ষে যেতে শুরু করে, তাহলে আমাদের খুঁজে বের করতে হবে যে পথটি সম্পূর্ণ করার কোন উপায় আছে কি, যদি এটি সম্ভব হয় তবে ইঁদুরের জন্য সঠিক পথ চিহ্নিত করুন৷

গোলকধাঁধাটি একটি বাইনারি ম্যাট্রিক্স ব্যবহার করে দেওয়া হয়েছে, যেখানে এটি 1 দিয়ে চিহ্নিত করা হয়েছে, এটি একটি বৈধ পথ, অন্যথায় একটি অবরুদ্ধ ঘরের জন্য 0৷

দ্রষ্টব্য: ইঁদুর কেবল দুই দিকে যেতে পারে, হয় ডানে বা নিচে।

ইনপুট এবং আউটপুট

Input:
This algorithm will take the maze as a matrix.
In the matrix, the value 1 indicates the free space and 0 indicates the wall or blocked area.


In this diagram, the top-left circle indicates the starting point and the bottom-right circle indicates the ending point.
Output:
It will display a matrix. From that matrix, we can find the path of the rat to reach the destination point.

অ্যালগরিদম

এটি বৈধ(x, y)৷

ইনপুট: x এবং y বিন্দু গোলকধাঁধায়।

আউটপুট: (x,y) স্থানটি বৈধ হলে সত্য, অন্যথায় মিথ্যা।

Begin
   if x and y are in range and (x,y) place is not blocked, then
      return true
   return false
End

solveRatMaze(x, y)

ইনপুট − প্রারম্ভিক বিন্দু x এবং y।

আউটপুট − গন্তব্যে পৌঁছানোর জন্য ইঁদুরকে অনুসরণ করার পথ, অন্যথায় মিথ্যা।

Begin
   if (x,y) is the bottom right corner, then
      mark the place as 1
      return true
   if isValidPlace(x, y) = true, then
      mark (x, y) place as 1
      if solveRatMaze(x+1, y) = true, then //for forward movement
         return true
      if solveRatMaze(x, y+1) = true, then //for down movement
         return true
      mark (x,y) as 0 when backtracks
      return false
   return false
End

উদাহরণ

#include<iostream>
#define N 5
using namespace std;

int maze[N][N]  =  {
   {1, 0, 0, 0, 0},
   {1, 1, 0, 1, 0},
   {0, 1, 1, 1, 0},
   {0, 0, 0, 1, 0},
   {1, 1, 1, 1, 1}
};

int sol[N][N];         //final solution of the maze path is stored here
void showPath() {
   for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++)
         cout << sol[i][j] << " ";
      cout << endl;
   }
}

bool isValidPlace(int x, int y) {      //function to check place is inside the maze and have value 1
   if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
      return true;
   return false;
}

bool solveRatMaze(int x, int y) {
   if(x == N-1 && y == N-1) {       //when (x,y) is the bottom right room
      sol[x][y] = 1;
      return true;
   }

   if(isValidPlace(x, y) == true) {     //check whether (x,y) is valid or not
      sol[x][y] = 1; //set 1, when it is valid place
      if (solveRatMaze(x+1, y) == true)       //find path by moving right direction
         return true;
      if (solveRatMaze(x, y+1) == true)         //when x direction is blocked, go for bottom direction
         return true;
      sol[x][y] = 0;         //if both are closed, there is no path
      return false;
   }  
   return false;
}

bool findSolution() {
   if(solveRatMaze(0, 0) == false) {
      cout << "There is no path";
      return false;
   }
   showPath();
   return true;
}

int main() {
   findSolution();
}

আউটপুট