1
struct Position {
2
  long long int pos;
3
  long long int speed;
4
  long long int moves;
5

6
  Position(int pos, int speed, int moves) {
7
    this->pos = pos;
8
    this->speed = speed;
9
    this->moves = moves;
10
  }
11
};
12

13
class Solution {
14
 public:
15
  int racecar(int target) {
16
    queue<Position> q;
17
    Position p(0, 1, 0);
18
    q.push(p);
19

20
    set<pair<long long int, long long int>> s;
21

22
    while (!q.empty()) {
23
      Position u = q.front();
24
      q.pop();
25

26
      if (u.pos == target) return u.moves;
27

28
      if (s.find({u.pos, u.speed}) != s.end())
29
        continue;
30
      else {
31
        s.insert({u.pos, u.speed});
32

33
        // only cases when you might need to move backwards
34
        if ((u.pos + u.speed > target && u.speed > 0) ||
35
            (u.pos + u.speed < target && u.speed < 0)) {
36
          long long int speed = u.speed > 0 ? -1 : 1;
37
          Position bkwd(u.pos, speed, u.moves + 1);
38
          q.push(bkwd);
39
        }
40

41
        Position fwd(u.pos + u.speed, 2 * u.speed, u.moves + 1);
42
        q.push(fwd);
43
      }
44
    }
45

46
    return -1;
47
  }
48
};