ধরুন আমাদের কাছে অ-ঋণাত্মক পূর্ণসংখ্যার অ্যারের একটি অ্যারে আছে, আমরা প্রাথমিকভাবে অ্যারের শুরু সূচকে অবস্থান করছি। যখন আমরা সূচক i এ উপস্থিত থাকি, তখন আমরা i + arr[i] বা i - arr[i] তে লাফ দিতে পারি, আমরা 0 মান সহ কোনো সূচকে পৌঁছাতে পারি কিনা তা পরীক্ষা করতে পারি। আমাদের মনে রাখতে হবে যে আমরা এর বাইরে যেতে পারি না। যে কোনো সময় অ্যারে। তাই ইনপুট যদি হয়:arr =[4,2,3,0,3,1,2] এবং 5 থেকে শুরু হয়, তাহলে আউটপুট সত্য হবে, যেমন মুভ 5 → 4 → 1 → 3, বা 5 → 6 → 4 → 1 → 3.
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n :=arr এর আকার
- একটি সারি q সংজ্ঞায়িত করুন, q-তে সূচনা সন্নিবেশ করুন, পরিদর্শন করা বলে একটি সেট সংজ্ঞায়িত করুন এবং পরিদর্শন করা সেটটিতে সূচনা সন্নিবেশ করুন
- যখন সারি খালি নয়,
- curr :=q এর সামনের উপাদান, q থেকে সামনের উপাদান মুছে দিন
- যদি অ্যারে[curr] 0 হয়, তাহলে true রিটার্ন করুন
- যদি curr + arr[curr]
- q-তে curr + arr[curr] ঢোকান
- ভিজিটেড এ curr + arr[curr] ঢোকান
- যদি curr - arr[curr]>=0 এবং curr - arr[curr] পরিদর্শন করা সেটে উপস্থিত না থাকে, তাহলে
- ক্যুতে কার - arr[curr] q এ প্রবেশ করান
- ক্যুর সন্নিবেশ করুন - arr[curr] পরিদর্শন করা হয়েছে
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#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
