Xe đua trong C ++

Giả sử chúng ta có một chiếc ô tô, khởi hành ở vị trí 0 và tốc độ +1 trên một trục số vô hạn. Xe chạy tự động theo trình tự hướng dẫn A:tăng tốc và R - lùi. Khi chúng tôi nhận được chỉ dẫn "A", xe của chúng tôi sẽ thực hiện những việc sau -

vị trí:=vị trí + tốc độ, sau đó tốc độ =tốc độ * 2.

Khi chúng tôi nhận được chỉ dẫn "R", xe của chúng tôi sẽ làm như sau -

nếu tốc độ là dương thì tốc độ =-1,
nếu không thì tốc độ =1.

Ví dụ:sau khi thực hiện hướng dẫn "AAR", xe của chúng tôi đi đến vị trí 0-> 1-> 3-> 3 và tốc độ đi đến 1-> 2-> 4 -> - 1.

Bây giờ, giả sử chúng ta có một số vị trí mục tiêu; chúng ta phải tìm độ dài của chuỗi hướng dẫn ngắn nhất để đạt được điều đó.

Vì vậy, nếu đầu vào là target =6, thì đầu ra sẽ là 5 vì một trong các chuỗi có thể là AAARA, chuỗi vị trí sẽ là 0-> 1-> 3-> 7-> 7-> 6

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một tập hợp đã truy cập
Xác định một hàng đợi q
chèn {0, 1} vào q
cho mức khởi tạo:=0, khi không phải q trống, hãy cập nhật (tăng mức 1), thực hiện -
- để khởi tạo k:=kích thước của q, khi k> 0, cập nhật (giảm k đi 1), thực hiện -
  - Xác định một cặp curr:=phần tử phía trước của q, xóa phần tử khỏi q
  - nếu đầu tiên của curr giống với target, thì -
    - mức trả lại
  - chuyển tiếp:=đầu tiên của curr + thứ hai của curr
  - forwardSpeed:=giây của curr * 2
  - key:=convert forward to string concatenate "*" concatenate convert forwardSpeed to string
  - nếu chuyển tiếp> 0 và | chuyển tiếp - mục tiêu |
  - chèn khóa vào đã truy cập
  - chèn {forward, forwardSpeed} vào q
- key:=chuyển đầu tiên của curr thành chuỗi nối "*" nối 0 khi thứ hai của curr> 0, nếu không thì -1
- nếu curr.first> 0 và | target - curr.first |
- chèn khóa vào đã truy cập
- chèn {curr.first, (nếu curr.second> 0, thì -1, nếu không thì 1}) vào q

trả về -1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Xe đua trong C ++

Ví dụ

Đầu vào

Đầu ra