मान लीजिए एक मेंढक है जो एक नदी पार कर रहा है। नदी x इकाइयों में विभाजित है और प्रत्येक इकाई पर एक पत्थर हो सकता है। मेंढक एक पत्थर पर कूद सकता है, लेकिन पानी पर नहीं। यहां हमारे पास आरोही क्रम में क्रमबद्ध पत्थरों की स्थितियों की एक सूची है, हमें जांचना है कि क्या मेंढक अंतिम पत्थर पर उतरकर नदी पार करने में सक्षम है या नहीं। प्रारंभ में, मेंढक पहले पत्थर पर है और मान लें कि पहली कूद 1 इकाई की होनी चाहिए।
जब मेंढक की वर्तमान कूद k इकाई की थी, तो उसकी अगली कूद या तो k - 1, k, या k + 1 इकाई की होनी चाहिए। और मेंढक केवल आगे की दिशा में कूद सकता है।
तो यदि दी गई सरणी [0,1,3,4,5,7,9,10,12] जैसी है, तो उत्तर true होगा, क्योंकि मेंढक 1 इकाई कूदकर दूसरे पत्थर पर, 2 इकाई कूदकर तीसरे पत्थर पर, फिर 2 इकाई कूदकर चौथे पत्थर पर, फिर 3 इकाई कूदकर छठे पत्थर पर, 4 इकाई कूदकर सातवें पत्थर पर और अंत में 5 इकाई कूदकर आठवें पत्थर पर पहुंच सकता है।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- visited नामक एक मैप परिभाषित करें
- एक फ़ंक्शन canCross() परिभाषित करें, जो एक सरणी stones, pos इसे 0 से आरंभ करें, k इसे 0 से आरंभ करें, लेगा,
- key := pos OR (left shift k 11 बिट्स)
- यदि key visited में मौजूद है, तो -
- visited[key] लौटाएं
- i := pos + 1 से आरंभ करें, जब i < stones का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें -
- gap := stones[i] - stones[pos]
- यदि gap < k - 1, तो -
- निम्न भाग को अनदेखा करें, अगले पुनरावृत्ति पर जाएं
- यदि gap > k + 1, तो -
- visited[key] := false
- false लौटाएं
- यदि canCross(stones, i, gap) को कॉल करना शून्येतर है, तो -
- visited[key] = true
- true लौटाएं
- visited[key] = true जब (pos stones के आकार - 1 के समान है) अन्यथा false
- visited[key] लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public: unordered_map < lli, int > visited; bool canCross(vector<int>& stones, int pos = 0, int k = 0) { lli key = pos | k << 11; if(visited.find(key) != visited.end())return visited[key]; for(int i = pos + 1; i < stones.size(); i++){ int gap = stones[i] - stones[pos]; if(gap < k - 1)continue; if(gap > k + 1){ return visited[key] = false; } if(canCross(stones, i, gap))return visited[key] = true; } return visited[key] = (pos == stones.size() - 1); } }; main(){ Solution ob; vector<int> v = {0,1,3,5,6,8,12,17}; cout << (ob.canCross(v)); }इनपुट
0,1,3,5,6,8,12,17
आउटपुट
1
