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

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

यदि इनपुट है -

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

तो आउटपुट 3 होगा, हमें इंडेक्स 0 से 4 से 3 से 9 तक तीन कूद की आवश्यकता है।

हल करने के चरण

एक मानचित्र m परिभाषित करें
n := arr का आकार
प्रत्येक इंडेक्स i के लिए, i को m[arr[i]] के अंत में डालें
visited सेट में 0 डालें, कतार q परिभाषित करें
स्तर दर स्तर BFS करें: वर्तमान नोड के लिए, यदि यह n-1 है तो स्तर लौटाएं
i-1, i+1 और समान मान वाले सभी इंडेक्स पर जाएं यदि वे visited में नहीं हैं
समान मान वाले इंडेक्स की सूची को m से मिटा दें ताकि दोबारा विज़िट न हो
यदि कतार खाली हो जाए तो -1 लौटाएं

उदाहरण

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

class Solution { 
public: 
    int minJumps(vector<int>& arr) { 
        map<int, vector<int> > m; 
        int n = arr.size(); 
        for (int i = 0; i < n; i++) { 
            m[arr[i]].push_back(i); 
        } 
        set<int> visited; 
        visited.insert(0); 
        queue<int> q; 
        q.push(0); 
        for (int lvl = 0; !q.empty(); lvl++) { 
            int sz = q.size(); 
            while (sz--) { 
                int curr = q.front(); 
                q.pop(); 
                if (curr == n - 1) return lvl; 
                int i = curr; 
                if (i - 1 >= 0 && !visited.count(i - 1)) { 
                    q.push(i - 1); 
                    visited.insert(i - 1); 
                } 
                if (i + 1 < n && !visited.count(i + 1)) { 
                    q.push(i + 1); 
                    visited.insert(i + 1); 
                } 
                for (int j = 0; j < m[arr[curr]].size(); j++) { 
                    if (!visited.count(m[arr[curr]][j])) { 
                        q.push(m[arr[curr]][j]); 
                        visited.insert(m[arr[curr]][j]); 
                    } 
                } 
                if (m.count(arr[curr])) { 
                    m.erase(arr[curr]); 
                } 
            } 
        } 
        return -1; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<int> v = {20,-5,-5,25,20,5,5,5,1,25}; 
    cout << (ob.minJumps(v)); 
    return 0; 
}

इनपुट

{20,-5,-5,25,20,5,5,5,1,25}