C++ में रेस कार (Race Car) समस्या

मान लीजिए हमारे पास एक कार है, जो अनंत संख्या रेखा पर स्थिति 0 और गति +1 से शुरू होती है। कार निर्देशों के एक क्रम के अनुसार स्वचालित रूप से चलती है: A - त्वरण (accelerate) के लिए और R - रिवर्स (reverse) के लिए। जब हमें निर्देश "A" मिलता है, तो हमारी कार निम्न करती है -

स्थिति := स्थिति + गति, फिर गति = गति * 2।

जब हमें निर्देश "R" मिलता है, तो हमारी कार निम्न करती है -

यदि गति धनात्मक है तो गति = -1,
अन्यथा गति = 1।

उदाहरण के लिए, निर्देश "AAR" निष्पादित करने के बाद, हमारी कार स्थितियों 0->1->3->3 पर जाती है, और गति 1->2->4->-1 हो जाती है।

अब मान लीजिए हमारे पास कोई लक्ष्य स्थिति है; हमें वहां पहुंचने के लिए निर्देशों के सबसे छोटे अनुक्रम की लंबाई ज्ञात करनी है।

तो, यदि इनपुट target = 6 जैसा है, तो आउटपुट 5 होगा क्योंकि संभावित अनुक्रमों में से एक AAARA है, स्थिति अनुक्रम 0->1->3->7->7->6 होगा।

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

एक सेट visited परिभाषित करें
एक क्यू q परिभाषित करें
{ 0, 1 } को q में डालें
level := 0 से प्रारंभ करें, जब q खाली नहीं है, level बढ़ाते हुए, करें -
- k := q के आकार से प्रारंभ करें, जब k > 0, k घटाते हुए, करें -
  - curr := q के सामने का तत्व, q से तत्व हटाएं
  - यदि curr का पहला भाग target के समान है, तो -
    - level वापस करें
  - forward := curr का पहला भाग + curr का दूसरा भाग
  - forwardSpeed := curr का दूसरा भाग * 2
  - key := forward को स्ट्रिंग में बदलें + " * " + forwardSpeed को स्ट्रिंग में बदलें
  - यदि forward > 0 और |forward - target| < target और key visited में नहीं है, तो -
    - key को visited में डालें
    - { forward, forwardSpeed } को q में डालें
  - key := curr के पहले भाग को स्ट्रिंग में बदलें + " * " + (curr का दूसरा भाग > 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)); }