C++ . में रेस कार

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

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

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

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

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

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

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

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

देखे गए एक सेट को परिभाषित करें
एक कतार q परिभाषित करें
क्यू में { 0, 1 } डालें
इनिशियलाइज़ लेवल के लिए:=0, जब q खाली न हो, तो अपडेट करें (1 से लेवल बढ़ाएँ), −
- इनिशियलाइज़ k :=q के आकार के लिए, जब k> 0, अपडेट करें (k को 1 से घटाएँ), करें -
  - एक जोड़ी वक्र परिभाषित करें:=q का अगला तत्व, q से तत्व हटाएं
  - यदि पहला curr लक्ष्य के समान है, तो −
    - वापसी स्तर
  - आगे :=कर्व का पहला + कर्व का दूसरा
  - फॉरवर्डस्पीड :=दूसरा करंट * 2
  - कुंजी :=स्ट्रिंग में आगे कनवर्ट करें concatenate "*" concatenate फॉरवर्डस्पीड को स्ट्रिंग में कनवर्ट करें
  - अगर आगे> 0 और |आगे - लक्ष्य| <लक्ष्य और कुंजी नहीं देखी गई है, तो −
    - भेजे गए में कुंजी डालें
    - क्यू में {फॉरवर्ड, फॉरवर्डस्पीड} डालें
  - कुंजी :=पहले curr को स्ट्रिंग में बदलें "*" concatenate 0 जब curr का दूसरा> 0, अन्यथा -1
  - अगर curr.first> 0 और |target - curr.first| <लक्ष्य और कुंजी का दौरा नहीं किया गया है, तो −
    - भेजे गए में कुंजी डालें
    - सम्मिलित करें { curr.first, (यदि curr.second> 0, फिर -1, अन्यथा 1 })
वापसी -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));
}