1
class Solution {
2
  public int racecar(int target) {
3
    Queue<int[]> queue = new LinkedList<>();
4
    queue.add(new int[] {0, 1, 0});
5
    Set<String> visited = new HashSet<>();
6

7
    while (!queue.isEmpty()) {
8
      int[] item = queue.poll();
9
      int currPos = item[0];
10
      int currSpeed = item[1];
11
      int distance = item[2];
12

13
      if (currPos == target) return distance;
14

15
      // Choosing A
16
      int nextPos = currPos + currSpeed;
17
      int nextSpeed = currSpeed * 2;
18
      String posSpeed =
19
          new StringBuilder().append(nextPos).append(",").append(nextSpeed).toString();
20

21
      // If the particular state (position & speed) is not encountered earlier then we explore that
22
      // state
23
      // And we also check if the nextPos is not beyond twice the size of target, then there is no
24
      // point in exploring that route
25
      if (!visited.contains(posSpeed) && Math.abs(nextPos) < 2 * target) {
26
        visited.add(posSpeed);
27
        queue.add(new int[] {nextPos, nextSpeed, distance + 1});
28
      }
29

30
      // Choosing R
31
      // We go in reverse only when we are moving away from the target in the positive or in the
32
      // negative direction
33
      if ((currPos + currSpeed > target && currSpeed > 0)
34
          || (currPos + currSpeed < target && currSpeed < 0)) {
35
        nextSpeed = currSpeed > 0 ? -1 : 1;
36
        posSpeed = new StringBuilder().append(currPos).append(",").append(nextSpeed).toString();
37

38
        if (!visited.contains(posSpeed) && Math.abs(currPos) < 2 * target) {
39
          visited.add(posSpeed);
40
          queue.add(new int[] {currPos, nextSpeed, distance + 1});
41
        }
42
      }
43
    }
44
    return -1;
45
  }
46
}