सी ++ में मेंढक कूदो

मान लीजिए कोई मेंढक है जो नदी पार कर रहा है। नदी को x इकाइयों में विभाजित किया गया है और प्रत्येक इकाई में एक पत्थर हो सकता है। मेंढक पत्थर पर कूद सकता है, लेकिन पानी नहीं। यहां हमारे पास क्रमबद्ध आरोही क्रम क्रम में पत्थरों की स्थिति की एक सूची है, हमें यह जांचना है कि मेंढक आखिरी पत्थर पर उतरकर नदी पार करने में सक्षम है या नहीं। प्रारंभ में, मेंढक पहले पत्थर पर है और मान लें कि पहली छलांग 1 इकाई की होनी चाहिए।

जब मेंढक की वर्तमान छलांग k इकाई थी, तब उसकी अगली छलांग या तो k-1, k, या k + 1 इकाई होनी चाहिए। और मेंढक केवल आगे की दिशा में ही कूद सकता है।

तो यदि दी गई सरणी [0,1,3,4,5,7,9,10,12] की तरह है, तो उत्तर सही होगा, मेंढक 1 इकाई से दूसरे पत्थर तक, 2 इकाइयों से कूद सकता है तीसरा पत्थर, फिर 2 इकाई से चौथा पत्थर, फिर 3 इकाई से छठा पत्थर, 4 इकाई से 7वां पत्थर और अंत में 5 इकाई से 8वां पत्थर।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• विज़िट किए गए मानचित्र को परिभाषित करें
• एक फ़ंक्शन को परिभाषित करें canCross(), यह एक सरणी पत्थर लेगा, इसे 0 से प्रारंभ करें, k इसे 0 से प्रारंभ करें,
• कुंजी :=pos OR (बाएं शिफ़्ट k 11 बिट)
• यदि विज़िट में कुंजी मौजूद है, तो −
  • विजिट की गई वापसी[कुंजी]
• इनिशियलाइज़ i :=pos + 1 के लिए, जब i <स्टोन्स का आकार, अपडेट करें (i से 1 तक बढ़ाएँ), करें −
  • अंतराल:=पत्थर[i] - पत्थर[स्थिति]
  • अगर गैप
  • निम्न भाग पर ध्यान न दें, अगले भाग पर जाएं
• अगर गैप> k + 1, तो −
  • विज़िट किया [कुंजी] :=असत्य
  • झूठी वापसी
• यदि फ़ंक्शन को कॉल करें canCross(stones, i, gap) गैर-शून्य है, तो −
  • विज़िट किया [कुंजी] =सत्य
  • सही लौटें

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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