सी++ में जंप गेम IV

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

तो, अगर इनपुट पसंद है,

सी++ में जंप गेम IV

तो आउटपुट 3 होगा, हमें इंडेक्स 0 से 4 से 3 से 9 तक तीन छलांग चाहिए।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

एक नक्शा परिभाषित करें मी
n :=गिरफ्तारी का आकार
इनिशियलाइज़ i :=0 के लिए, जब i
- m[arr[i]]
  . के अंत में i डालें
m[arr[i]]
. के अंत में i डालें
विज़िट किए गए में 0 डालें
एक कतार को परिभाषित करें q
lvl प्रारंभ करने के लिए :=0, जब q खाली न हो, अद्यतन करें (1 से lvl बढ़ाएँ), do−
- sz :=q का आकार
- जबकि sz गैर-शून्य है, प्रत्येक पुनरावृत्ति में sz को 1 से घटाएं -
  - curr :=q का पहला तत्व
  - q से तत्व हटाएं
  - अगर curr n-1 के समान है, तो
    - वापसी एलवीएल
  - मैं :=वक्र
  - अगर i - 1>=0 और नहीं i - 1 विज़िट किया गया है, तो -
    - q में i-1 डालें
    - विज़िट किए गए में i - 1 डालें
  - अगर i + 1
    - q में i + 1 डालें
    - विज़िट किए गए में i + 1 डालें
  - इनिशियलाइज़ j :=0 के लिए, जब j
    - अगर (m[arr[curr], j]) का दौरा नहीं किया गया है, तो -
      - q में m[arr[curr], j] डालें
      - देखे गए में m[arr[curr], j] डालें
  - अगर arr[curr] m में नहीं है, तो -
    - m
      . से arr[curr] हटाएं
वापसी -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;
   }
};
main(){
   Solution ob;
   vector<int> v = {20,-5,-5,25,20,5,5,5,1,25};
   cout << (ob.minJumps(v));
}

इनपुट

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