LeetCode 1654. 到家的最少跳跃次数
题目描述
题意分析
从数轴位置零出发，每次向前跳
a或向后跳b，求到达位置x的最少跳跃次数。不能落在负数位置或forbidden中，也不能连续两次向后跳。只限制落点，允许跳过禁区位置，也允许先越过目标再跳回来。起点就是目标时需要零跳；没有合法路线时返回
-1。
解法：带方向状态的 BFS
核心思路
[!blue]
每次跳跃的代价都是一步，因此用 BFS 按跳数逐层搜索。状态不能只有位置，还要记录
jumpedBack：零表示上一步不是后跳、允许下一步后跳；一表示刚后跳过、下一步只能前跳。同一个位置的这两种状态允许的下一步不同，不能共用访问标记。前跳到
pos + a后状态变为零；只有当前状态为零，才允许后跳到pos - b，后跳后状态变为一。落点合法且该状态未访问时入队，并立即标记，避免重复扩展。数轴没有天然右界，需要证明可以只搜索到
limit = max(x, maxForbidden) + a + b。令M = max(x, maxForbidden)。若a >= b，位置超过x + b后，即使先后跳一次也仍在目标右侧；此后每次后跳之前必须前跳，合计位移a-b非负，不可能再回到目标。因此不需要进入更远位置。若
a < b，考虑一条合法路线中超过M+a+b的最高位置p。到达它的最后一步只能前跳；前一步也必须是前跳，否则那次后跳的出发点为p-a+b>p，与最高位置矛盾。离开最高点只能后跳，所以局部一定出现“前、前、后”。将这三步改为“前、后、前”，起止位置与步数都不变，也不会出现连续后跳。唯一新增落点是
p-a-b>M，高于所有禁区且非负，其余落点仍合法，同时避开原最高点。不断替换过高峰值，就能把任意可行路线变成步数相同、不过此上界的路线，所以截断不会丢掉最短解。有界后最多只有
2 * (limit + 1)种状态。每层固定处理进入该层时的队列长度，新状态留到下一层；第一次取出目标的层数就是最少跳数。
解题步骤
- 将禁区放入集合，计算最大禁区及搜索上界。
- 从状态
(0, 0)开始，标记并入队，层数为零。- 每层取固定数量的状态；当前位置等于目标时返回层数。
- 尝试上界以内的前跳；当前允许后跳时，再尝试非负的后跳。
- 只将不在禁区且未访问的完整状态入队，处理完一层后跳数加一。
- 队列耗尽仍未到目标则返回
-1。
代码实现
class Solution {
// 同一个位置在 "上一步是否向后跳" 两种状态下后续选择不同，访问标记必须区分这两类状态。
public int minimumJumps(int[] forbidden, int a, int b, int x) {
Set<Integer> blocked = new HashSet<>();
int maxForbidden = 0;
for (int pos : forbidden) {
blocked.add(pos);
maxForbidden = Math.max(maxForbidden, pos);
}
int limit = Math.max(x, maxForbidden) + a + b;
boolean[][] visited = new boolean[limit + 1][2];
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[] {
0,
0
});
visited[0][0] = true;
int steps = 0;
while (!queue.isEmpty()) {
// 固定本层状态数量，本轮新增状态统一留到下一跳。
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cur = queue.poll();
int pos = cur[0];
int jumpedBack = cur[1];
if (pos == x) {
return steps;
}
int forward = pos + a;
if (forward <= limit && !blocked.contains(forward) && !visited[forward][0]) {
// 前跳恢复后跳权限，入队前标记避免重复状态。
visited[forward][0] = true;
queue.offer(new int[] {
forward,
0
});
}
// 只有上一步不是后跳，本轮才允许尝试后跳。
if (jumpedBack == 0) {
int backward = pos - b;
if (backward >= 0 && !blocked.contains(backward) && !visited[backward][1]) {
// 后跳落点进入禁止连续后跳的状态。
visited[backward][1] = true;
queue.offer(new int[] {
backward,
1
});
}
}
}
steps++;
}
return -1;
}
}
func minimumJumps(forbidden []int, a int, b int, x int) int {
// 同一个位置在 "上一步是否向后跳" 两种状态下后续选择不同，访问标记必须区分这两类状态。
blocked := make(map[int]struct{})
maxForbidden := 0
for _, pos := range forbidden {
blocked[pos] = struct{}{}
if pos > maxForbidden {
maxForbidden = pos
}
}
limit := maxInt(x, maxForbidden) + a + b
visited := make([][2]bool, limit+1)
queue := make([][2]int, 0)
queue = append(queue, [2]int{
0,
0,
})
visited[0][0] = true
steps := 0
for head := 0; head < len(queue); {
// 固定本层状态数量，本轮新增状态统一留到下一跳。
size := len(queue) - head
for i := 0; i < size; i++ {
cur := queue[head]
head++
pos := cur[0]
jumpedBack := cur[1]
if pos == x {
return steps
}
forward := pos + a
if forward <= limit && !contains(blocked, forward) && !visited[forward][0] {
// 前跳恢复后跳权限，入队前标记避免重复状态。
visited[forward][0] = true
queue = append(queue, [2]int{
forward,
0,
})
}
// 只有上一步不是后跳，本轮才允许尝试后跳。
if jumpedBack == 0 {
backward := pos - b
if backward >= 0 && !contains(blocked, backward) && !visited[backward][1] {
// 后跳落点进入禁止连续后跳的状态。
visited[backward][1] = true
queue = append(queue, [2]int{
backward,
1,
})
}
}
}
steps++
}
return -1
}
func contains(blocked map[int]struct{}, pos int) bool {
_, ok := blocked[pos]
return ok
}
func maxInt(a int, b int) int {
if a > b {
return a
}
return b
}
复杂度分析
- 时间复杂度：期望 $O(U+F)$，其中 $U$ 为位置上界，$F$ 为禁区数。最多处理两倍位置数的状态，每个状态尝试两种跳法，集合查询平均常数时间。
- 空间复杂度：$O(U+F)$，用于两类访问标记、队列及禁区集合。
关键点总结
[!green]
- 上一步方向影响后续动作，必须进入状态，而不能只记录位置。
- 每条合法转移都花一次跳跃，BFS 的层数对应最短步数。
- 搜索上界由可调整路径或不可回退性质保证，不能随意截在目标处。
- 入队即标记完整状态，保证每种位置与权限组合至多入队一次。
易错点总结
[!yellow]
- 只按位置去重，会把后跳权限不同的到达方式合并，漏掉有效路线。
- 后跳后仍保留后跳权限，违反禁止连续后跳的规则。
- 将搜索范围限制为
0..x，会漏掉必须先越过目标再回来的路线。- 只检查是否跨过禁区会增加题目没有的限制，真正需要检查的是落点。
- 不固定每层大小就遍历新加入状态，会把不同跳数混在同一层，导致答案计数错误。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1129. 颜色交替的最短路径 | 中等 | 同样必须把上一步类型纳入BFS状态，本题需要记是否刚向后跳，不能只按坐标去重。 |
| 1306. 跳跃游戏 III | 中等 | 原题跳长由当前位置决定，本题前后步长固定但禁止连续后跳，状态规则不同。 |