C++ में भूलभुलैया समस्या का समाधान

समस्या विवरण

मान लीजिए एक गेंद एक भूलभुलैया में है जिसमें खाली स्थान और दीवारें हैं। गेंद किसी भी दिशा में (ऊपर, नीचे, बाएं, दाएं) लुढ़ककर खाली रास्तों से गुजर सकती है, लेकिन यह तब तक नहीं रुकेगी जब तक यह दीवार से न टकरा जाए। जब गेंद रुकती है, तो यह अगली दिशा चुन सकती है।

हमें गेंद की प्रारंभिक स्थिति, गंतव्य और भूलभुलैया दी गई है। हमें जांचना है कि क्या गेंद गंतव्य पर रुक सकती है। भूलभुलैया को एक 2D सरणी द्वारा दर्शाया गया है। यहां 1 दीवार को इंगित करता है और 0 खाली स्थान को। भूलभुलैया की सीमाएं सभी दीवारें हैं। प्रारंभ और गंतव्य निर्देशांक पंक्ति और स्तंभ सूचकांकों द्वारा दर्शाए गए हैं।

उदाहरण

यदि इनपुट इस तरह की भूलभुलैया है:

प्रारंभ स्थिति (0, 4) है और गंतव्य स्थिति (4, 4) है, तो आउटपुट true होगा। एक संभावित मार्ग है: बाएं फिर नीचे फिर दाएं।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम BFS (ब्रेडथ-फर्स्ट सर्च) एल्गोरिदम का उपयोग करेंगे:

1. एक कतार (queue) का उपयोग करके उन सभी स्थितियों को ट्रैक करें जहां गेंद रुक सकती है
2. एक सेट (visited) का उपयोग करके पहले से देखी गई स्थितियों को रिकॉर्ड करें
3. प्रारंभ स्थिति से शुरू करके, चार दिशाओं में गेंद को तब तक लुढ़काएं जब तक दीवार न मिल जाए
4. जहां गेंद रुकती है, उन स्थितियों को कतार में जोड़ें यदि वे पहले नहीं देखी गई हैं
5. यदि गंतव्य स्थिति तक पहुंच जाते हैं, तो true लौटाएं
6. यदि कतार खाली हो जाती है और गंतव्य नहीं मिलता, तो false लौटाएं

C++ कार्यान्वयन

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    bool hasPath(vector<vector<int>>& grid, vector<int>& start, vector<int>& destination) { 
        int n = grid.size(); 
        int m = grid[0].size(); 
        queue<vector<int>> q; 
        q.push(start); 
        set<vector<int>> visited; 
        visited.insert(start); 
        
        while (!q.empty()) { 
            vector<int> curr = q.front(); 
            q.pop(); 
            int x = curr[0]; 
            int y = curr[1]; 
            
            if (destination[0] == x && destination[1] == y) 
                return true; 
            
            // नीचे की ओर लुढ़कना
            int i = x; 
            while (i + 1 < n && !grid[i + 1][y]) 
                i++; 
            if (!visited.count({ i, y })) { 
                visited.insert({ i, y }); 
                q.push({ i, y }); 
            } 
            
            // ऊपर की ओर लुढ़कना
            i = x; 
            while (i - 1 >= 0 && !grid[i - 1][y]) 
                i--; 
            if (!visited.count({ i, y })) { 
                visited.insert({ i, y }); 
                q.push({ i, y }); 
            } 
            
            // दाएं की ओर लुढ़कना
            i = y; 
            while (i + 1 < m && !grid[x][i + 1]) 
                i++; 
            if (!visited.count({ x, i })) { 
                visited.insert({ x, i }); 
                q.push({ x, i }); 
            } 
            
            // बाएं की ओर लुढ़कना
            i = y; 
            while (i - 1 >= 0 && !grid[x][i - 1]) 
                i--; 
            if (!visited.count({ x, i })) { 
                visited.insert({ x, i }); 
                q.push({ x, i }); 
            } 
        } 
        return false; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<vector<int>> v = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}}; 
    vector<int> v1 = {0,4}, v2 = {4,4}; 
    cout << (ob.hasPath(v, v1, v2)); 
    return 0;
}

इनपुट

{{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}},{0,4},{4,4}

आउटपुट

1