C++-এ ফ্রগ জাম্প (Frog Jump) সমস্যা

ফ্রগ জাম্প সমস্যা

একটি বাঙ নদী পার করতে চায়। নদীর সরণি ধাপে ভাগ করা আছে এবং কিছু স্থানে পাথর আছে। বাঙটি শুধু পাথরের ওপর লাফিয়ে পার করতে পারে। পাথরদের অবস্থান ক্রমবর্ধমান ক্রমে দেওয়া আছে। বাঙটি প্রথম পাথরে থেকে শুরু করে এবং প্রথম লাফি অবশ্যই ১ ইউনিট হতে হবে।

যদি বর্তমান লাফি k ইউনিট হয়, তবে পরবর্তী লাফি হবে k-1, k, বা k+1 ইউনিট। বাঙটি শুধু ফরওয়ার্ড দিয়ে লাফাতে পারে। শেষ পাথরে পৌঁছাতে পারলে true, না পারলে false ফেরত দিন।

উদাহরণ: [0,1,3,5,6,8,12,17] → true

সমাধানের পদ্ধতি (মেমোইজেশন সহ DFS)

• একটি ভিজিটেড ম্যাপ visited রাখুন: কী = pos | (k << 11)
• canCross(stones, pos, k) ফাংশন:
  • ভিজিটেড চেক করুন
  • pos+1 থেকে শেষ পাথর পর্যন্ত লুপ:
    • gap = stones[i] - stones[pos]
    • যদি gap < k-1, আगे যান
    • যদি , false ফেরত দিন (আর কোনো পাথর 닿ে না)
    • রিকার্সিভলি canCross(stones, i, gap) কল করুন
    • যদি true পাওয়া যায়, মেমোইজ করে true ফেরত দিন
  • শেষ পাথরে পৌঁছালে true, অন্যথায় false

C++ কোড উদাহরণ

#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);
    }
};

int main() {
    Solution ob;
    vector<int> v = {0,1,3,5,6,8,12,17};
    cout << (ob.canCross(v));
    return 0;
}

ইনপুট

0,1,3,5,6,8,12,17

আউটপুট

1