###### tags: `LeetCode` `Hard` `Queue` `Dynamic Programming` `BFS`
# LeetCode #818 [Race Car](https://leetcode.com/problems/race-car/)
### (Hard)

你的賽車起始停留在位置 0，速度為 +1，正行駛在一個無限長的數軸上。 （車也可以向負數方向行駛。）

你的車會根據一系列由 A（加速）和 R（倒車）組成的指令進行自動駕駛 。

當車得到指令 "A" 時, 將會做出以下操作： position += speed, speed *= 2。

當車得到指令 "R" 時, 將會做出以下操作：如果當前速度是正數，則將車速調整為 speed = -1 ；否則將車速調整為 speed = 1。  (當前所處位置不變。)

例如，當得到一系列指令 "AAR" 後, 你的車將會走過位置 0->1->3->3，並且速度變化為 1->2->4->-1。

現在給定一個目標位置，請給出能夠到達目標位置的最短指令列表的長度。

---
有兩種指令:
* 'A':位置更新為原位置加上速度並且再加速, 速度變兩倍。
* 'R':調頭, 速度為正數則變為-1, 反之則變為+1。

目標位置上限為10000, 因此在位置加上速度大於10000之前都可以一直加速, 並把加速後的結果放入佇列中(成為下一次操作)。 此外, 當位置超過目標位置且速度為正時, 需要調頭(速度為負責不用, 因為正朝向目標前進), 以及當位置小於目標位置且速度為負時也需要調頭(同理, 此時速度為正的話也不需要調頭, 正在朝目標前進)。

當佇列組合中有數組的位置等同於目標位置時, 回傳該數組中的指令數。

---

class Solution {
public:
    int racecar(int target) {
        queue<vector<int>> q;//{position, speed, steps}
        q.push({0,1,0});
        while(!q.empty()){
            for(int i=q.size();i>0;i++){
                auto v = q.front();q.pop();
                int pos = v[0], speed = v[1], steps = v[2];
                if(pos==target)return steps;
                if((pos+speed)<=10000&&(pos+speed)>0)
                    q.push({pos+speed, 2*speed, steps+1});//+'A'
                if((pos+speed)>target&&speed>0)
                    q.push({pos, -1, steps+1});//+'R'
                if((pos+speed)<target&&speed<=0)
                    q.push({pos, 1, steps+1});//+'R'
            }
        }
        return -1;
    }
};