C++ এ রেস কার

ধরুন আমাদের একটি গাড়ি আছে, যেটি 0 পজিশন থেকে শুরু হয় এবং একটি অসীম সংখ্যা লাইনে গতি +1 হয়। গাড়িটি স্বয়ংক্রিয়ভাবে চলে নির্দেশাবলীর একটি ক্রম অনুসারে A:ত্বরণের জন্য এবং R − বিপরীতের জন্য। যখন আমরা একটি নির্দেশ "A" পাই, আমাদের গাড়ি নিম্নলিখিতগুলি করে -

৷

অবস্থান :=অবস্থান + গতি, তারপর গতি =গতি * 2।

যখন আমরা একটি নির্দেশ "R" পাই, তখন আমাদের গাড়ি নিম্নলিখিতগুলি করে −

৷

যদি গতি ধনাত্মক হয় তবে গতি =-1,
অন্যথায় গতি =1।

উদাহরণস্বরূপ, "AAR" নির্দেশাবলী কার্যকর করার পরে, আমাদের গাড়ি 0->1->3->3 পজিশনে যায় এবং গতি 1->2->4->-1 হয়।

এখন ধরুন আমাদের কিছু টার্গেট পজিশন আছে; সেখানে যাওয়ার জন্য আমাদের নির্দেশাবলীর সংক্ষিপ্ততম ক্রমটির দৈর্ঘ্য খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট টার্গেট =6 এর মত হয়, তাহলে আউটপুট 5 হবে কারণ সম্ভাব্য ক্রমগুলির মধ্যে একটি হল AAARA, অবস্থানের ক্রম হবে 0->1->3->7->7->6

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

একটি পরিদর্শন করা সেট সংজ্ঞায়িত করুন
একটি সারি q সংজ্ঞায়িত করুন
q তে { 0, 1 } ঢোকান
সূচনা স্তরের জন্য :=0, যখন q খালি না থাকে, আপডেট করুন (লেভেল 1 দ্বারা বাড়ান), করুন −
- আরম্ভ করার জন্য k :=q এর আকার, যখন k> 0, আপডেট করুন (k 1 দ্বারা কম করুন), −
  - এক জোড়া curr সংজ্ঞায়িত করুন :=q এর সামনের উপাদান, q থেকে উপাদান মুছুন
  - যদি curr-এর প্রথমটি লক্ষ্যের সমান হয়, তাহলে −
    - রিটার্ন লেভেল
  - ফরওয়ার্ড :=curr এর প্রথম + curr এর সেকেন্ড
  - forwardSpeed :=curr * 2 এর সেকেন্ড
  - কী :=ফরওয়ার্ড স্ট্রিং কনকাটেনেটে রূপান্তর করুন " * " কনকাটেনেট ফরওয়ার্ডস্পীডকে স্ট্রিংয়ে রূপান্তর করুন
  - যদি ফরোয়ার্ড> 0 এবং |ফরোয়ার্ড - টার্গেট|
  - ভিজিটেড-এ কী ঢোকান
  - q তে { forward, forwardSpeed } ঢোকান
- কী :=curr-এর প্রথম স্ট্রিং কনকাটেনেট " * " concatenate 0 এ রূপান্তর করুন যখন curr এর সেকেন্ড> 0, অন্যথায় -1
- যদি curr.first> 0 এবং |টার্গেট - curr.first| <লক্ষ্য এবং কী পরিদর্শন করা হয় না, তারপর −
  - ভিজিটেড-এ কী ঢোকান
  - ক্যুতে { 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));
}