Race-Car

class Solution {
    public int racecar(int target) {
        Queue<Pair<Integer, Integer>> queue = new LinkedList();
        queue.add(new Pair(0, 1));
        Map<Pair<Integer, Integer>, Integer> dist = new HashMap();
        dist.put(new Pair(0, 1), 0);

        while (!queue.isEmpty()) {
            Pair<Integer, Integer> node = queue.poll();
            int pos = node.getKey(), spd = node.getValue();
            if (pos == target) {
                return dist.get(node);
            }
            if (Math.abs(pos) > 20000) {
                continue;
            }

            Pair<Integer, Integer>[] states = new Pair[2];
            states[0] = new Pair(pos + spd, spd * 2);
            states[1] = new Pair(pos, -spd / Math.abs(spd));

            for (Pair<Integer, Integer> state : states) {
                if (!dist.containsKey(state)) {
                    dist.put(state, dist.getOrDefault(node, 0) + 1);
                    queue.offer(state);
                }
            }
        }

        throw null;
    }
}