सी ++ चूहा एक भूलभुलैया में कई चरणों के साथ या कूदने की अनुमति है

एक एन * एन ग्रिड भूलभुलैया को देखते हुए। हमारा चूहा ग्रिड के ऊपरी बाएँ कोने में मौजूद है। अब चूहे केवल नीचे या आगे बढ़ सकते हैं, और यदि और केवल अगर ब्लॉक के पास गैर-शून्य मान है तो अब इस भिन्नता में चूहे को कई छलांग लगाने की अनुमति है। चूहा वर्तमान सेल से जो अधिकतम छलांग ले सकता है, वह सेल में मौजूद संख्या है, और अब आपको यह पता लगाने का काम सौंपा गया है कि क्या चूहा ग्रिड के निचले दाएं कोने तक पहुंच सकता है, उदाहरण के लिए -

Input : { { {1, 1, 1, 1},
{2, 0, 0, 2},
{3, 1, 0, 0},
{0, 0, 0, 1}
},
Output : { {1, 1, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 0},
{0, 0, 0, 1}
}

Input : {
{2, 1, 0, 0},
{2, 0, 0, 1},
{0, 1, 0, 1},
{0, 0, 0, 1}
}
Output: Path doesn't exist

समाधान खोजने के लिए दृष्टिकोण

इस दृष्टिकोण में, हम हर उस पथ को ट्रैक करने के लिए बैकट्रैकिंग का उपयोग करेंगे जो चूहा अब ले सकता है। यदि चूहा किसी भी रास्ते से हमारी मंजिल तक पहुंच जाता है तो हम उस रास्ते के लिए सच होकर लौट जाते हैं और फिर उस रास्ते को छाप देते हैं। अन्यथा, हम प्रिंट करते हैं कि पथ मौजूद नहीं है।

उदाहरण

 
#include <bits/stdc++.h>
using namespace std;
#define N 4 // size of our grid
bool solveMaze(int maze[N][N], int x, int y, // recursive function for finding the path
    int sol[N][N]){
        if (x == N - 1 && y == N - 1) { // if we reached our goal we return true and mark our goal as 1
            sol[x][y] = 1;
            return true;
    }
    if (x >= 0 && y >= 0 && x < N && y < N && maze[x][y]) {
        sol[x][y] = 1; // we include this index as a path
        for (int i = 1; i <= maze[x][y] && i < N; i++) { // as maze[x][y] denotes the number of jumps you can take                                             //so we check for every jump in every direction
            if (solveMaze(maze, x + i, y, sol) == true) // jumping right
               return true;
            if (solveMaze(maze, x, y + i, sol) == true) // jumping downward
               return true;
        }
        sol[x][y] = 0; // if none are true then the path doesn't exist
                   //or the path doesn't contain current cell in it
        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 << "Path doesn't exist\n";
    return 0;
}

आउटपुट

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

उपरोक्त कोड की व्याख्या

उपरोक्त दृष्टिकोण में, हम प्रत्येक पथ की जांच करते हैं जो यह हमारे वर्तमान सेल से बना सकता है, और जब हम इसकी जांच करते हैं, तो हम पथों को एक के रूप में चिह्नित करते हैं। जब हमारा मार्ग गतिरोध पर पहुंचता है, तो हम जांचते हैं कि वह गतिरोध हमारी मंजिल है या नहीं। अब, यदि वह हमारा गंतव्य नहीं है, तो हम पीछे जाते हैं, और जैसे ही हम पीछे जाते हैं, हम सेल को 0 के रूप में चिह्नित करते हैं क्योंकि यह पथ मान्य नहीं है, और इस तरह हमारा कोड आगे बढ़ता है।

निष्कर्ष

इस ट्यूटोरियल में, हम चूहे को एक भूलभुलैया में हल करते हैं जिसमें कई चरणों या छलांग की अनुमति है। हमने इस समस्या के लिए C++ प्रोग्राम और संपूर्ण दृष्टिकोण (Normal) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह ट्यूटोरियल मददगार लगा होगा।