रैट इन ए मेज़ समस्या

इस समस्या में, N x N आकार का एक दिया गया मेज़ है। स्रोत और गंतव्य स्थान क्रमशः टॉप-लेफ्ट सेल और बॉटम राइट सेल हैं। कुछ सेल मूव करने के लिए वैध हैं और कुछ सेल ब्लॉक हैं। यदि एक चूहा स्टार्ट वर्टेक्स से डेस्टिनेशन वर्टेक्स तक चलना शुरू करता है, तो हमें यह ढूंढना है कि क्या पथ पूरा करने का कोई तरीका है, यदि संभव है तो चूहे के लिए सही पथ चिह्नित करें।

मेज़ को बाइनरी मैट्रिक्स का उपयोग करके दिया गया है, जहां 1 से चिह्नित है, यह एक वैध पथ है, अन्यथा ब्लॉक सेल के लिए 0।

नोट: चूहा केवल दो दिशाओं में चल सकता है, या तो दाएं या नीचे।

इनपुट और आउटपुट

इनपुट: यह एल्गोरिदम मेज़ को मैट्रिक्स के रूप में लेगा। मैट्रिक्स में, मान 1 मुक्त स्थान को इंगित करता है और 0 दीवार या ब्लॉक क्षेत्र को इंगित करता है।  इस आरेख में, टॉप-लेफ्ट सर्कल प्रारंभिक बिंदु को इंगित करता है और बॉटम-राइट सर्कल अंतिम बिंदु को इंगित करता है। आउटपुट: यह एक मैट्रिक्स प्रदर्शित करेगा। उस मैट्रिक्स से, हम चूहे का पथ ढूंढ सकते हैं जो गंतव्य बिंदु तक पहुंचने के लिए अनुसरण करता है। 

एल्गोरिदम

isValid(x, y)

इनपुट: मेज़ में x और y बिंदु

आउटपुट: True यदि (x,y) स्थान वैध है, अन्यथा false

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

आउटपुट- चूहे द्वारा गंतव्य तक पहुंचने के लिए अनुसरण करने का पथ, अन्यथा false

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 #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(); }

आउटपुट

1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1