LeetCode 1654. 到家的最少跳跃次数

题目描述

有一只跳蚤住在数轴上的位置 0 处。它希望跳到位置 x（x > 0），但必须遵循以下规则：

1. 它可以向前跳（数轴正方向）a 个单位。
2. 它可以向后跳（数轴负方向）b 个单位。
3. 它不能连续向后跳两次。
4. 它不能跳到某些禁止的位置（给定一个数组 forbidden，其中的位置不能进入）。
5. 它的位置不能超过某个边界。题目隐含的条件是，位置不能超过 max(furthest, x) + b 的某个安全范围，实际实现中我们一般取上限为 max(x, max(forbidden)) + a + b 或更大以确保不会错过可行路径。

你需要返回跳蚤到达 x 的最少跳跃次数。如果无法到达，返回 -1。

示例

输入：forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
输出：3
解释：向前跳 3 步三次到达 9。

解题思路

这是一个状态空间搜索问题，但带有额外的约束（不能连续向后跳两次）。
我们可以用广度优先搜索（BFS） 来求最短路径，因为每一步跳跃的代价是 1（每次跳跃算一步）。
但状态不能只用当前位置表示，因为能否向后跳取决于上一步是否已经向后跳了。
所以状态是 (当前位置, 是否是从向后跳到达的)。

为什么 BFS 可行

• 每一步跳跃是单位花费，BFS 第一次到达目标位置时，步数最少。
• 需要防止无限扩展：位置有上限，且要避开 forbidden 位置。
• 需要记录访问过的状态避免重复。

详细步骤

1. 确定状态和搜索空间
状态是 (pos, backward_used)，其中：

• pos 是当前在数轴上的整数位置。
• backward_used 表示上一步是否是向后跳（1 表示是，0 表示不是）。
  （如果上一步是向后跳，则这一步不能再向后跳。）

我们要从初始状态 (0, 0) 开始，走到 (x, 0) 或 (x, 1) 都可以（因为最后一步是向前还是向后不影响到达终点）。

2. 确定位置上限
如果无限制向上搜索，可能无限向前走（当 a > b 时可能越走越远却无法回来）。
题目虽然没有显式给上限，但可以通过分析得到：

• 如果位置超过了 max(x, max(forbidden)) + a + b 甚至更大，再往右走就难以回到 x（因为要向左跳 b，如果当前位置已经远大于 x+b，可能需要很多步回来，但实际上最优路径不会超过某个范围）。
• 常见安全上限设为 6000 或通过公式 max(x, max(forbidden)) + a + b，因为如果位置超过 x+b 后，再往前跳 a 就更远了，要回来必须向后跳 b，而连续不能向后跳两次，所以不会无限右移。
  实际测试中，上限取 max(x, max(forbidden)) + a + b 是安全的，这里我们可以取 max(2000, x + a + b) 或更大保证覆盖。

3. BFS 过程
队列元素：(位置, backward_used, 步数)。
初始队列：(0, 0, 0)。
访问标记：visited[pos][backward_used] 表示这个状态是否访问过，避免重复。
forbidden 位置在任何情况下都不能进入。

状态转移：

• 如果 backward_used == 0，表示上一步不是向后跳，那么这一步可以：
  1. 向前跳 a 到达 pos + a，新状态 (pos+a, 0)。
  2. 向后跳 b 到达 pos - b，新状态 (pos-b, 1)。
• 如果 backward_used == 1，表示上一步是向后跳，这一步只能向前跳 a 到达 (pos+a, 0)。

跳跃后位置必须 >= 0 且 <= MAX 且不在 forbidden 中。

4. 终止条件
当从队列中取出 pos == x 时，返回步数。

5. 如果队列为空还没找到，返回 -1。

举例说明

以示例 forbidden=[14,4,18,1,15], a=3, b=15, x=9 为例：

初始：(0,0,0)
向前跳 3 → (3,0,1)
向前跳 3 → (6,0,2)
向前跳 3 → (9,0,3) 到达，返回 3。

注意事项

• forbidden 可能包含 0，那直接无法开始（但题目没有这种情况，因为起始位置 0 是允许的）。
• 上限 MAX 必须足够大，否则会错过路径。比如 a=1,b=2,x=1000，需要多次来回，位置不会超过 x+b+某值，但取 6000 或 x+max(a,b)*2 是安全的，这里取 max(x, max(forbidden)) + a + b 是常用公式。
• visited 要区分 backward_used，因为同一个位置，上一步是向后跳来的和向前跳来的，后续可行动作不同。

BFS 实现框架

def minimumJumps(forbidden, a, b, x):
    forbidden_set = set(forbidden)
    # 上限
    max_val = max(x, max(forbidden, default=0)) + a + b + 5
    # visited[pos][0/1]
    visited = [[False, False] for _ in range(max_val + 1)]
    
    from collections import deque
    queue = deque()
    queue.append((0, 0, 0))  # (位置, 是否上步是向后跳, 步数)
    visited[0][0] = True
    
    while queue:
        pos, back_used, steps = queue.popleft()
        if pos == x:
            return steps
        
        # 向前跳
        nxt = pos + a
        if nxt <= max_val and nxt not in forbidden_set and not visited[nxt][0]:
            visited[nxt][0] = True
            queue.append((nxt, 0, steps + 1))
        
        # 向后跳（必须上一步不是向后跳，且不能跳到 forbidden，且位置>=0）
        if back_used == 0:
            nxt = pos - b
            if nxt >= 0 and nxt not in forbidden_set and not visited[nxt][1]:
                visited[nxt][1] = True
                queue.append((nxt, 1, steps + 1))
    
    return -1

复杂度分析

• 位置上限是 O(max(x, max(forbidden)) + a + b)，记为 M。
• 每个位置最多访问 2 次（两种 back_used 状态），所以时间复杂度 O(M)。
• 空间复杂度 O(M) 用于 visited 和队列。

这样我们就得到了一个在状态空间中进行 BFS 寻找最短路径的完整解法。