मान लीजिए कि हमारे पास गैर-ऋणात्मक पूर्णांकों की एक सरणी है, हम प्रारंभ में सरणी के प्रारंभ अनुक्रमणिका पर स्थित हैं। जब हम इंडेक्स 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 :=गिरफ्तारी का आकार
- एक कतार q परिभाषित करें, q में प्रारंभ डालें, विज़िट किए गए सेट को परिभाषित करें, और देखे गए सेट में प्रारंभ डालें
- जबकि कतार खाली नहीं है,
- curr :=q का अगला तत्व, q से सामने वाला तत्व हटाएं
- यदि सरणी [curr] 0 है, तो सही लौटें
- यदि curr + arr[curr]
- q में curr + arr[curr] डालें
- भ्रमण में curr + arr[curr] डालें
- अगर curr - arr[curr]>=0 और curr - arr[curr] विज़िट किए गए सेट में मौजूद नहीं है, तो
- q में curr - arr[curr] डालें
- सम्मिलित करें curr - 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