A bug at position 0 can jump forward a or backward b. Some positions are forbidden. Find min jumps to reach x.
Input: forbidden=[14,4,18,1,15], a=3, b=15, x=9 → Output: 3
Input: forbidden=[8,3,16,6,12,20], a=15, b=13, x=11 → Output: -1
BFS with states (position, lastJump). Bound search space to avoid infinite loops.
- BFS with (position, direction) state
- Bound max position to max(forbidden)+a+b+x
- Track visited positions and last move direction
- At each step try forward jump (always) and backward jump (if last was not backward)
- Return steps when x reached
public int minimumJumps(int[] forbidden, int a, int b, int x) {
Set<Integer> banned = new HashSet<>();
for (int f : forbidden) banned.add(f);
int bound = Arrays.stream(forbidden).max().orElse(0) + a + b + x;
Set<String> visited = new HashSet<>();
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0}); // {pos, lastDir: 0=none/fwd, 1=back}
visited.add("0,0");
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
int[] cur = queue.poll();
int pos = cur[0], dir = cur[1];
if (pos == x) return steps;
int fwd = pos + a;
if (fwd <= bound && !banned.contains(fwd) && visited.add(fwd + ",0"))
queue.offer(new int[]{fwd, 0});
if (dir != 1) {
int bck = pos - b;
if (bck >= 0 && !banned.contains(bck) && visited.add(bck + ",1"))
queue.offer(new int[]{bck, 1});
}
}
steps++;
}
return -1;
}
- Time Complexity: O(n)
- Space Complexity: O(n)