মনে করুন একটি নন-নেগেটিভ পূর্ণসংখ্যার অ্যারে `arr` আছে, আমরা প্রাথমিকভাবে অ্যারেতে `start` ইন্ডেক্সে অবস্থিত। যখন আমরা ইন্ডেক্স `i`-তে থাকি, আমরা `i + arr[i]` বা `i - arr[i]`-এ জাম্প করতে পারি, চেক করতে হবে কি আমরা ০ মানযুক্ত যেকোনো ইন্ডেক্সে পৌঁছাতে পারি। মনে রাখতে হবে যে আমরা যেকোনো সময় অ্যারের বাইরে জাম্প করতে পারব না। যদি ইনপুট হয়: `arr = [4,2,3,0,3,1,2]` এবং `start = 5`, তবে আউটপুট হবে `true`, কারণ 5 → 4 → 1 → 3, অথবা 5 → 6 → 4 → 1 → 3 পথে যেতে পারি।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -
- `n` := `arr`-এর আকার
- একটি কিউ `q` সংজ্ঞায়িত করুন, `start`-কে `q`-তে ইনসার্ট করুন, একটি সেট `visited` সংজ্ঞায়িত করুন, এবং `start`-কে `visited`-এ ইনসার্ট করুন
- যদি কিউ খালি না থাকে,
- `curr := q`-এর ফ্রন্ট এলিমেন্ট, `q`-এর ফ্রন্ট এলিমেন্ট ডিলিট করুন
- যদি `arr[curr]` 0 হয়, তবে `true` রিটার্ন করুন
- যদি `curr + arr[curr] < n` এবং `curr + arr[curr]` `visited` সেটে না থাকে, তবে
- `curr + arr[curr]`-কে `q`-তে ইনসার্ট করুন
- `curr + arr[curr]`-কে `visited`-এ ইনসার্ট করুন
- যদি `curr - arr[curr] >= 0` এবং `curr - arr[curr]` `visited` সেটে না থাকে, তবে
- `curr - arr[curr]`-কে `q`-তে ইনসার্ট করুন
- `curr - arr[curr]`-কে `visited`-এ ইনসার্ট করুন
- `false` রিটার্ন করুন
উদাহরণ
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন -
#include <bits/stdc++.h> using namespace std; class Solution { public: bool canReach(vector<int>& arr, int start) { int n = arr.size(); queue <int> q; q.push(start); set <int> visited; visited.insert(start); while(!q.empty()){ int curr = q.front(); q.pop(); if(arr[curr] == 0)return true; if(curr + arr[curr] < n && !visited.count(curr + arr[curr])){ q.push(curr + arr[curr]); visited.insert(curr + arr[curr]); } if(curr - arr[curr] >= 0 && !visited.count(curr - arr[curr])){ q.push(curr - arr[curr]); visited.insert(curr - arr[curr]); } } return false; } }; main(){ vector<int> v = {4,2,3,0,3,1,2}; Solution ob; cout << (ob.canReach(v, 5)); }ইনপুট
[4,2,3,0,3,1,2] 5
আউটপুট
1
