ปัญหารถแข่ง (Race Car) ใน C++

ภาพรวมปัญหา

สมมติว่ามีรถเริ่มต้นที่ตำแหน่ง 0 และความเร็ว +1 บนเส้นจำนวนที่ไม่มีที่สิ้นสุด รถจะทำงานอัตโนมัติตามลำดับคำสั่ง A (Accelerate/เร่งความเร็ว) และ R (Reverse/ย้อนกลับ):

• คำสั่ง "A": ตำแหน่ง = ตำแหน่ง + ความเร็ว, แล้วความเร็ว = ความเร็ว × 2
• คำสั่ง "R": ถ้าความเร็วเป็นบวก ความเร็ว = -1, มิฉะนั้น ความเร็ว = 1

ตัวอย่าง: คำสั่ง "AAR" ทำให้ตำแหน่งเปลี่ยน 0→1→3→3 และความเร็ว 1→2→4→-1

โจทย์: กำหนดตำแหน่งเป้าหมาย (target) หาความยาวลำดับคำสั่งสั้นที่สุดเพื่อไปถึงเป้าหมาย

ตัวอย่าง

target = 6 → Output = 5 (ลำดับคำสั่ง AAARA: ตำแหน่ง 0→1→3→7→7→6)

แนวทางแก้ปัญหา (BFS)

• ใช้ BFS ค้นหาสถานะ (ตำแหน่ง, ความเร็ว) โดยแต่ละระดับ = จำนวนคำสั่ง
• เก็บสถานะที่เคยเยี่ยมชมด้วย set (key = "position*speed")
• จากสถานะปัจจุบัน สร้าง 2 สถานะใหม่: กด A (เร่ง) และกด R (ย้อน)
• ตัด枝 (prune) สถานะที่ไกลจากเป้าหมายเกินไป หรือเคยเยี่ยมชมแล้ว
• เมื่อเจอตำแหน่งเป้าหมาย คืนค่าระดับปัจจุบัน

ตัวอย่างโปรแกรม

#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;
                
                // กด A: เร่งความเร็ว
                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});
                }
                
                // กด R: ย้อนกลับ
                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));
}

Input

6

Output

5