from collections import deque
class Solution:
def minimumJumps(self, forbidden, a, b, x):
forbidden = set(forbidden)
max_limit = max([x] + list(forbidden)) + a + b + 2000 # Safe upper bound
visited = set()
queue = deque()
queue.append((0, 0, False)) # (position, jumps, last_jump_was_backward)
visited.add((0, False))
while queue:
pos, jumps, back = queue.popleft()
if pos == x:
return jumps
# Move forward
next_fwd = pos + a
if (0 <= next_fwd <= max_limit and
next_fwd not in forbidden and
(next_fwd, False) not in visited):
visited.add((next_fwd, False))
queue.append((next_fwd, jumps + 1, False))
# Move backward (only if last jump wasn't backward)
if not back:
next_bwd = pos - b
if (0 <= next_bwd and
next_bwd not in forbidden and
(next_bwd, True) not in visited):
visited.add((next_bwd, True))
queue.append((next_bwd, jumps + 1, True))
return -1
#include <vector>
#include <queue>
#include <unordered_set>
#include <tuple>
using namespace std;
class Solution {
public:
int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
unordered_set<int> forb(forbidden.begin(), forbidden.end());
int max_limit = max(x, *max_element(forbidden.begin(), forbidden.end())) + a + b + 2000;
queue<tuple<int, int, bool>> q; // position, jumps, last was backward?
unordered_set<long long> visited; // encode (pos, back) as pos*2 + back
q.push({0, 0, false});
visited.insert(0LL * 2 + 0);
while (!q.empty()) {
auto [pos, jumps, back] = q.front(); q.pop();
if (pos == x) return jumps;
int next_fwd = pos + a;
if (next_fwd >= 0 && next_fwd <= max_limit && !forb.count(next_fwd) && !visited.count((long long)next_fwd * 2 + 0)) {
visited.insert((long long)next_fwd * 2 + 0);
q.push({next_fwd, jumps + 1, false});
}
if (!back) {
int next_bwd = pos - b;
if (next_bwd >= 0 && !forb.count(next_bwd) && !visited.count((long long)next_bwd * 2 + 1)) {
visited.insert((long long)next_bwd * 2 + 1);
q.push({next_bwd, jumps + 1, true});
}
}
}
return -1;
}
};
import java.util.*;
class Solution {
public int minimumJumps(int[] forbidden, int a, int b, int x) {
Set<Integer> forb = new HashSet<>();
for (int f : forbidden) forb.add(f);
int maxLimit = Math.max(x, Arrays.stream(forbidden).max().orElse(0)) + a + b + 2000;
Queue<int[]> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.offer(new int[]{0, 0, 0}); // pos, jumps, lastBack
visited.add("0,0");
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int pos = curr[0], jumps = curr[1], back = curr[2];
if (pos == x) return jumps;
int nextFwd = pos + a;
if (nextFwd >= 0 && nextFwd <= maxLimit && !forb.contains(nextFwd) && !visited.contains(nextFwd + ",0")) {
visited.add(nextFwd + ",0");
queue.offer(new int[]{nextFwd, jumps + 1, 0});
}
if (back == 0) {
int nextBwd = pos - b;
if (nextBwd >= 0 && !forb.contains(nextBwd) && !visited.contains(nextBwd + ",1")) {
visited.add(nextBwd + ",1");
queue.offer(new int[]{nextBwd, jumps + 1, 1});
}
}
}
return -1;
}
}
/**
* @param {number[]} forbidden
* @param {number} a
* @param {number} b
* @param {number} x
* @return {number}
*/
var minimumJumps = function(forbidden, a, b, x) {
const forb = new Set(forbidden);
const maxLimit = Math.max(x, ...forbidden) + a + b + 2000;
const queue = [[0, 0, false]]; // [pos, jumps, lastBack]
const visited = new Set();
visited.add("0,false");
while (queue.length) {
const [pos, jumps, back] = queue.shift();
if (pos === x) return jumps;
const nextFwd = pos + a;
if (nextFwd >= 0 && nextFwd <= maxLimit && !forb.has(nextFwd) && !visited.has(nextFwd + ",false")) {
visited.add(nextFwd + ",false");
queue.push([nextFwd, jumps + 1, false]);
}
if (!back) {
const nextBwd = pos - b;
if (nextBwd >= 0 && !forb.has(nextBwd) && !visited.has(nextBwd + ",true")) {
visited.add(nextBwd + ",true");
queue.push([nextBwd, jumps + 1, true]);
}
}
}
return -1;
};
You are given a list forbidden of forbidden positions on a one-dimensional number line, two positive integers a and b representing jump distances, and an integer x representing your target position. You start at position 0 and want to reach position x using the minimum number of jumps.
On each move, you can:
a units (i.e., from curr to curr + a).b units (i.e., from curr to curr - b), but you cannot jump backward twice in a row.forbidden and cannot go to negative positions.
Return the minimum number of jumps needed to reach x, or -1 if it is impossible.
Let's think about the problem in terms of states and transitions. Each position you land on is a state, and you can move to new states by jumping forward or (sometimes) backward. However, you have some restrictions:
0 to x while following the rules, which is a classic scenario for Breadth-First Search (BFS).
To avoid cycles and infinite loops, we need to remember which states we've already visited. Since the possibility of a backward jump depends on whether the previous move was backward, our state should include both the position and whether the last jump was backward.
We use Breadth-First Search (BFS) to find the shortest sequence of jumps to reach x:
(position, last_jump_was_backward).0 with last_jump_was_backward = False.(position, last_jump_was_backward) pairs.x, return the number of jumps.x, return -1.max(x, max(forbidden)) + a + b + buffer.
Let's consider the input:
forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
At each step, the algorithm checks if a backward jump is possible and valid, but in this case, only forward jumps are needed. The BFS ensures that the shortest path (fewest jumps) is found.
The BFS ensures that each state is processed at most once, so the algorithm is efficient for the problem's constraints.
This problem is a variation of the shortest path search with additional constraints on movements. By modeling the state with both position and jump direction, and using BFS, we efficiently find the minimum number of jumps to reach the target. The key insight is to track not just positions, but also the history of the last jump, and to use a visited set to avoid cycles and redundant work. This approach is both elegant and practical for a wide range of similar "state machine" pathfinding problems.