मान लीजिए हमारे पास नॉन-नेगेटिव इंटीजर्स का एक ऐरे arr है, हम ऐरे के स्टार्ट इंडेक्स पर प्रारंभिक रूप से स्थित हैं। जब हम इंडेक्स i पर मौजूद होते हैं, तो हम i + arr[i] या i - arr[i] पर जंप कर सकते हैं, जांचें कि क्या हम मान 0 वाले किसी इंडेक्स तक पहुंच सकते हैं। हमें ध्यान रखना होगा कि हम किसी भी समय ऐरे के बाहर जंप नहीं कर सकते। यदि इनपुट इस प्रकार है: arr = [4,2,3,0,3,1,2] और स्टार्ट 5 से है, तो आउटपुट true होगा, जैसे मूव 5 → 4 → 1 → 3, या 5 → 6 → 4 → 1 → 3।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- n := arr का आकार
- एक क्यू q परिभाषित करें, स्टार्ट को q में डालें, visited नामक एक सेट परिभाषित करें, और स्टार्ट को visited सेट में डालें
- जब तक क्यू खाली नहीं है,
- curr := q का फ्रंट एलिमेंट, q से फ्रंट एलिमेंट डिलीट करें
- यदि array[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
