Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में एकाधिक चरणों या कूद की अनुमति के साथ रैट इन ए मेज़


एक 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 और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह ट्यूटोरियल मददगार लगा होगा।

  1. C++ में 3n स्लाइस वाली पिज्जा C++ में 3n स्लाइस वाली पिज्जा

    समस्या विवरण मान लीजिए 3n स्लाइस वाली एक पिज्जा है जिसके स्लाइस विभिन्न आकार के हैं। मैं और मेरे दो दोस्त पिज्जा के स्लाइस निम्नानुसार लेंगे: मैं कोई भी पिज्जा स्लाइस चुनूंगा। मेरा दोस्त अमल मेरे चुने हुए स्लाइस के एंटी-क्लॉकवाइज दिशा में अगला स्लाइस लेगा। मेरा दोस्त बिमल मेरे चुने हुए स्लाइस के क

  1. C++ में जंप गेम IV C++ में जंप गेम IV

    मान लीजिए हमारे पास arr नामक पूर्णांकों की एक सरणी है। हम प्रारंभ में इंडेक्स 0 पर हैं। एक चरण में हम इंडेक्स i से i + x पर कूद सकते हैं जहां: i + x = 0, j जहां: arr[i] और arr[j] समान हैं और i और j समान नहीं हैं। यहां n सरणी का आकार है। हमें सरणी के अंतिम इंडेक्स तक पहुंचने के लिए न्यूनतम चरणों की स

  1. C++ में जंप गेम V C++ में जंप गेम V

    मान लीजिए हमारे पास arr नामक पूर्णांकों की एक सरणी और एक पूर्णांक d है। एक चरण में हम इंडेक्स i से कूद सकते हैं: i + x जहां: i + x < n और x की सीमा 1 से d है। = 0 और x की सीमा 1 से d है। arr[k] हो। हम सरणी के किसी भी इंडेक्स से कूदना शुरू कर सकते हैं। हमें अधिकतम इंडेक्स की संख्या ज्ञात करनी है ज