সি++-এ রেস কার (Race Car) সমস্যা

মনে করুন, একটি গাড়ি অবস্থান ০ এবং গতি +১ দিয়ে একটি অসীম সংখ্যা রেখায় শুরু করে। গাড়িটি স্বয়ংক্রিয়ভাবে নির্দেশাবলীর একটি অনুক্রম অনুসরণ করে: A (त्वরণ) এবং R (বিপরীত)।

• নির্দেশ "A" পাওয়ায়: position := position + speed, তারপর speed = speed * 2।
• নির্দেশ "R" পাওয়ায়: যদি speed ধনাত্মক হয় তবে speed = -1, অন্যথায় speed = 1।

উদাহরণস্বরূপ, "AAR" নির্দেশাবলী実行 করলে গাড়ির অবস্থান হবে 0→1→3→3 এবং গতি হবে 1→2→4→-1।

এখন একটি লক্ষ্য অবস্থা (target) দেওয়া থাকলে, সেখানে পৌঁছানোর জন্য ন্যূনতম নির্দেশাবলীর দৈর্ঘ্য বের করতে হবে।

যেমন, target = 6 হলে, আউটপুট হবে ৫। সম্ভাব্য একটি অনুক্রম হলো AAARA, যেখানে অবস্থান অনুক্রম হবে 0→1→3→7→7→6।

সমাধানের ধাপসমূহ

• একটি visited সেট এবং একটি কিউ q সংজ্ঞায়িত করুন
• {0, 1} কে q-তে ঢুকান
• level := 0 থেকে শুরু করে q খালি না হওয়া পর্যন্ত লুপ চালান
  • k := q.size() থেকে ১ পর্যন্ত লুপ চালান
    • curr := q-এর সামনের উপাদান, q থেকে মুছে ফেলুন
    • যদি curr.first == target হয়, তবে level রিটার্ন করুন
    • forward := curr.first + curr.second
    • forwardSpeed := curr.second * 2
    • key := to_string(forward) + "*" + to_string(forwardSpeed)
    • যদি forward > 0 এবং |forward - target| < target এবং key visited-এ নেই, তবে
      • key কে visited-এ ঢুকান, {forward, forwardSpeed} কে q-তে ঢুকান
    • key := to_string(curr.first) + "*" + to_string(curr.second > 0 ? -1 : 1)
    • যদি curr.first > 0 এবং |target - curr.first| < target এবং key visited-এ নেই, তবে
      • key কে visited-এ ঢুকান, {curr.first, (curr.second > 0 ? -1 : 1)} কে q-তে ঢুকান
• -1 রিটার্ন করুন

উদাহরণ

#include <bits/stdc++.h> using namespace std; class Solution { public:    int racecar(int target) {       unordered_set < string > visited;       queue < pair <int ,int> > q;       q. push({0, 1});       for(int level = 0; !q.empty(); level++){          for(int k = q.size(); k > 0; k-- ){             pair <int, int> curr = q.front();             q.pop();             if(curr.first == target) return level;             int forward = curr.first + curr.second;             int forwardSpeed = curr.second * 2;             string key = to_string(forward) + ""*"" + to_string(forwardSpeed);             if(forward > 0 && abs(forward - target) < target && !visited.count(key)){                visited.insert(key);                q.push({forward, forwardSpeed});             }             key = to_string(curr.first) + ""*"" + to_string(curr.second > 0 ? - 1: 1);             if(curr.first > 0 && abs(target - curr.first) < target && !visited.count(key)){                visited.insert(key);                q.push({curr.first, curr.second > 0 ? - 1: 1});             }          }       }       return -1;    } }; main(){    Solution ob;    cout << (ob.racecar(6)); }

ইনপুট

6

আউটপুট

5