818-1

class Solution {
public:
    struct state{
        int speed, position;
        state(int s, int pos){
            speed = s;
            position = pos;
        }
    };

    int racecar(int target) {
        queue<state> q;
        unordered_map<string, bool> vis;
        int distance = 0;
        q.push(state(1, 0));
        vis["1,0"] = true;

        // BFS on next states.
        while(!q.empty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                state cur = q.front(); q.pop();
                if(cur.position == target)
                    return distance;

                // Next move is A
                int nextPos = cur.position+cur.speed;
                int nextSpeed = cur.speed*2;
                if(nextPos == target)
                    return distance+1;
                string nextState = to_string(nextSpeed)+","+to_string(nextPos);
                if(!vis.count(nextState) && abs(nextPos-target) < target){
                    vis[nextState] = true;
                    q.push(state(nextSpeed, nextPos));
                }

                // Next move is R
                nextPos = cur.position;
                nextSpeed = (cur.speed > 0) ? -1 : 1;
                if(nextPos == target)
                    return distance+1;
                nextState = to_string(nextSpeed)+","+to_string(nextPos);
                if(!vis.count(nextState) && abs(nextPos-target) < target){
                    vis[nextState] = true;
                    q.push(state(nextSpeed, nextPos));
                }
            }
            distance++;
        }
        return -1;
    }
};