C++-এ জাম্প গেম IV (Jump Game IV)

ধরি arr নামক একটি ইন্টিজার অ্যারে দেওয়া আছে। আমরা শুরুর মধ্যে ইন্ডেক্স 0-এ আছি। এক স্টেপে আমরা ইন্ডেক্স i থেকে যেতে পারি –

i + x যেখানে: i + x < n
i - x যেখানে: i - x >= 0
j যেখানে: arr[i] এবং arr[j] সমান এবং i != j

এখানে n হলো অ্যারের আকার। অ্যারার শেষ ইন্ডেক্সে পৌঁছানোর জন্য ন্যূনতম স্টেপ বের করতে হবে।

ইনপুট যদি হয় –

তাহলে আউটপুট হবে 3, কারণ ইন্ডেক্স 0 থেকে 4, 4 থেকে 3, 3 থেকে 9 – এই তিনটি জাম্প দরকার।

সমাধানের ধাপসমূহ

m নামক একটি ম্যাপ সংজ্ঞায়িত করুন
n := arr এর আকার
i := 0 থেকে n-1 পর্যন্ত লুপ চালিয়ে i কে m[arr[i]]-এর শেষে যোগ করুন
visited সেটে 0 যোগ করুন
q নামক একটি কিউ সংজ্ঞায়িত করুন
lvl := 0 থেকে q খালি না হওয়া পর্যন্ত লুপ চালান –
- sz := q এর আকার
- sz কোনো 0 না হওয়া পর্যন্ত লুপ চালান –
  - curr := q-এর প্রথম উপাদান
  - q থেকে উপাদান মুছুন
  - যদি curr == n - 1 হয়, তবে –
    - lvl ফেরত দিন
  - i := curr
  - যদি i - 1 >= 0 এবং i - 1 visited-এ না থাকে, তবে –
    - i - 1 কে q এবং visited-এ যোগ করুন
  - যদি i + 1 < n এবং i + 1 visited-এ না থাকে, তবে –
    - i + 1 কে q এবং visited-এ যোগ করুন
  - j := 0 থেকে m[arr[curr]] এর আকার পর্যন্ত লুপ চালান –
    - যদি m[arr[curr], j] visited-এ না থাকে, তবে –
      - m[arr[curr], j] কে q এবং visited-এ যোগ করুন
  - যদি arr[curr] m-এ থাকে, তবে –
    - arr[curr] কে 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;    } }; 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}