एक n*n ग्रिड मेज़ दिया गया है। हमारा चूहा ग्रिड के ऊपरी बाएं कोने में मौजूद है। अब चूहे केवल नीचे या आगे बढ़ सकते हैं, यदि और केवल यदि ब्लॉक में एक गैर-शून्य मान है। अब इस विविधता में चूहे को कई कूद लेने की अनुमति है। चूहा वर्तमान सेल से अधिकतम कूद ले सकता है वह संख्या जो सेल में मौजूद है, और अब आपको यह खोजने का काम सौंपा गया है कि क्या चूहा ग्रिड के नीचे-दाएं कोने तक पहुंच सकता है, उदाहरण के लिए:
इनपुट: {{{1, 1, 1, 1}, {2, 0, 0, 2}, {3, 1, 0, 0}, {0, 0, 0, 1}},
आउटपुट: {{1, 1, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 0}, {0, 0, 0, 1}}
इनपुट: {{2, 1, 0, 0}, {2, 0, 0, 1}, {0, 1, 0, 1}, {0, 0, 0, 1}}
आउटपुट: पथ मौजूद नहीं है
समाधान खोजने का दृष्टिकोण
इस दृष्टिकोण में, हम बैकट्रैकिंग का उपयोग करेंगे ताकि हर पथ को ट्रैक किया जा सके जो चूहा ले सकता है। अब यदि चूहा किसी भी पथ से हमारे गंतव्य तक पहुंचता है, तो हम उस पथ के लिए true रिटर्न करते हैं और फिर पथ प्रिंट करते हैं। अन्यथा, हम प्रिंट करते हैं कि पथ मौजूद नहीं है।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
#define N 4 // हमारे ग्रिड का आकार
bool solveMaze(int maze[N][N], int x, int y, // पथ खोजने के लिए रिकर्सिव फंक्शन
int sol[N][N]) {
if (x == N - 1 && y == N - 1) { // यदि हम अपने लक्ष्य तक पहुंच गए तो हम true रिटर्न करते हैं और अपने लक्ष्य को 1 के रूप में चिह्नित करते हैं
sol[x][y] = 1;
return true;
}
if (x >= 0 && y >= 0 && x < N && y < N && maze[x][y]) {
sol[x][y] = 1; // हम इस इंडेक्स को पथ के रूप में शामिल करते हैं
for (int i = 1; i <= maze[x][y] && i < N; i++) { // चूंकि maze[x][y] उन कूदों की संख्या को दर्शाता है जो आप ले सकते हैं
// इसलिए हम हर दिशा में हर कूद के लिए जांच करते हैं
if (solveMaze(maze, x + i, y, sol) == true) // दाएं कूदना
return true;
if (solveMaze(maze, x, y + i, sol) == true) // नीचे कूदना
return true;
}
sol[x][y] = 0; // यदि कोई true नहीं है तो पथ मौजूद नहीं है
// या पथ में वर्तमान सेल नहीं है
return false;
}
return false;
}
int main() {
int maze[N][N] = {{2, 1, 0, 0}, {3, 0, 0, 1}, {0, 1, 0, 1}, {0, 0, 0, 1}};
int sol[N][N];
memset(sol, 0, sizeof(sol));
if (solveMaze(maze, 0, 0, sol)) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
cout << sol[i][j] << " ";
cout << "\n";
}
} else
cout << "पथ मौजूद नहीं है\n";
return 0;
}
आउटपुट
1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1
उपरोक्त कोड की व्याख्या
उपरोक्त दृष्टिकोण में, हम अपने वर्तमान सेल से बनाए जा सकने वाले हर पथ की जांच करते हैं, और जब हम जांच करते हैं, तो हम पथ को 1 के रूप में चिह्नित करते हैं। अब जब हमारा पथ डेड-एंड पर पहुंचता है, तो हम जांचते हैं कि वह डेड-एंड हमारा गंतव्य है या नहीं। अब, यदि वह हमारा गंतव्य नहीं है, तो हम बैकट्रैक करते हैं, और जैसे ही हम बैकट्रैक करते हैं, हम सेल को 0 के रूप में चिह्नित करते हैं क्योंकि यह पथ वैध नहीं है, और इस तरह हमारा कोड आगे बढ़ता है।
निष्कर्ष
इस ट्यूटोरियल में, हम एकाधिक चरणों या कूद की अनुमति के साथ रैट इन ए मेज़ को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और इसे हल करने के पूर्ण दृष्टिकोण (सामान्य) को भी सीखा। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह ट्यूटोरियल मददगार लगा होगा।