C++ এ জাম্প গেম IV

ধরুন আমাদের কাছে arr নামক পূর্ণসংখ্যার একটি অ্যারে আছে। আমরা প্রাথমিকভাবে সূচক 0 এ আছি। এক ধাপে আমরা সূচক i থেকে i + x এ যেতে পারি যেখানে:i + x =0. j যেখানে:arr[i] এবং arr[j] একই এবং i এবং j একই নয়। এখানে n হল অ্যারের আকার। অ্যারের শেষ সূচকে পৌঁছানোর জন্য আমাদের ন্যূনতম সংখ্যক ধাপ খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট মত হয়,

C++ এ জাম্প গেম IV

তাহলে আউটপুট 3 হবে, আমাদের সূচক 0 থেকে 4 থেকে 3 থেকে 9 পর্যন্ত তিনটি লাফ দিতে হবে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি মানচিত্র m
সংজ্ঞায়িত করুন
n :=arr এর আকার
আরম্ভ করার জন্য i :=0, যখন i
- m[arr[i]]
  এর শেষে i ঢোকান
m[arr[i]]
এর শেষে i ঢোকান
ভিজিট করা
-এ 0 ঢোকান
এক সারি q
সংজ্ঞায়িত করুন
lvl শুরু করার জন্য :=0, যখন q খালি না থাকে, আপডেট করুন (lvl 1 দ্বারা বাড়ান), do−
- sz :=q এর আকার
- যখন sz অ-শূন্য, প্রতিটি পুনরাবৃত্তিতে sz কমিয়ে 1 do −
  - curr :=q এর প্রথম উপাদান
  - q
    থেকে উপাদান মুছুন
  - যদি curr n - 1 এর মত হয়, তাহলে
    - ফিরুন lvl
  - আমি :=curr
  - যদি 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}