Race Car (Xe đua) trong C++

Xe bắt đầu tại vị trí 0, tốc độ +1 trên đường số vô hạn. Lệnh A (tăng tốc): position += speed; speed *= 2. Lệnh R (quay đầu): nếu tốc độ dương thì speed = -1, ngược lại speed = 1. Tìm độ dài chuỗi lệnh ngắn nhất để đến vị trí target.

Ví dụ

target = 6 → kết quả 5. Chuỗi AAARA: vị trí 0→1→3→7→7→6.

Thuật toán BFS

Duyệt trạng thái (position, speed) bằng BFS. Mỗi trạng thái sinh ra 2 trạng thái mới: tăng tốc (A) hoặc quay đầu (R). Dùng set visited lưu cặp "pos*speed" để tránh lặp. Giới hạn tìm kiếm: chỉ xét vị trí > 0 và khoảng cách đến target < target.

Chương trình C++

#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--) {
                auto curr = q.front(); q.pop();
                if(curr.first == target) return level;
                // Accelerate
                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});
                }
                // Reverse
                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;
    }
};

int main() {
    Solution ob;
    cout << ob.racecar(6);
    return 0;
}

Kết quả

5