C++ এ ব্যাঙ লাফিয়ে

ধরুন একটি ব্যাঙ আছে যেটি একটি নদী পার হচ্ছে। নদীটি x ইউনিটে বিভক্ত এবং প্রতিটি ইউনিটে একটি পাথর থাকতে পারে। ব্যাঙ পাথরের উপর ঝাঁপ দিতে পারে, কিন্তু জল নয়। এখানে আমাদের পাথরের অবস্থানের একটি তালিকা রয়েছে ক্রমবর্ধমান ক্রমানুসারে, আমাদের পরীক্ষা করতে হবে যে ব্যাঙটি শেষ পাথরে অবতরণ করে নদী পার হতে পারবে কি না। প্রাথমিকভাবে, ব্যাঙটি প্রথম পাথরের উপর থাকে এবং ধরে নেয় প্রথম লাফটি 1 ইউনিটের হতে হবে।

যখন ব্যাঙের বর্তমান লাফটি k ইউনিট ছিল, তখন তার পরবর্তী লাফটি অবশ্যই k - 1, k, অথবা k + 1 ইউনিট হতে হবে। এবং ব্যাঙ শুধুমাত্র সামনের দিকে ঝাঁপ দিতে পারে।

সুতরাং যদি প্রদত্ত অ্যারেটি [0,1,3,4,5,7,9,10,12] এর মত হয়, তবে উত্তরটি সত্য হবে যেমন, ব্যাঙটি 1 ইউনিট থেকে 2য় পাথরে, 2 ইউনিটে 3য় পাথর, তারপর আবার 2 ইউনিট থেকে 4র্থ পাথর, তারপর 3 ইউনিট থেকে 6ষ্ঠ পাথর, 4 ইউনিট থেকে 7ম পাথর এবং অবশেষে 5 ইউনিট থেকে 8ম পাথর।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• ভিজিটেড নামে একটি মানচিত্র সংজ্ঞায়িত করুন
• একটি ফাংশন সংজ্ঞায়িত করুন canCross(), এটি একটি অ্যারে স্টোন নেবে, pos 0 দিয়ে আরম্ভ করবে, k 0 দিয়ে আরম্ভ করবে,
• কী :=pos OR (বাম শিফট k 11 বিট)
• যদি পরিদর্শনে কী উপস্থিত থাকে, তাহলে −
  • রিটার্ন পরিদর্শন[কী]
• আরম্ভ করার জন্য i :=pos + 1, যখন i <পাথরের আকার, আপডেট করুন (i 1 দ্বারা বৃদ্ধি করুন), করুন −
  • গ্যাপ :=পাথর[i] - পাথর[pos]
  • যদি ফাঁক
  • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তিতে যান
• যদি ফাঁক> k + 1 হয়, তাহলে −
  • ভিজিট করা[কী] :=মিথ্যা
  • মিথ্যে ফেরত দিন
• যদি canCross(stones, i, gap) ফাংশনটিকে অ-শূন্য হয়, তাহলে −
  • 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