BFS解力扣1654最短跳跃次数-洪萨配资

对于 LeetCode 1654 “到家的最少跳跃次数”这道题，核心是使用广度优先搜索 (BFS)来寻找从起点0到目标位置x的最短路径。解题的关键在于对搜索空间进行合理的限制，并正确处理“不能连续向后跳”的约束。

问题解构与约束分析

约束条件	说明
跳跃规则	1. 向前跳`a`步。 2. 向后跳`b`步。
特殊限制	1.不能连续两次向后跳。 2. 不能跳到`forbidden`数组中的位置。 3. 不能跳到负数位置。
目标	从位置 `
0`出发，到达位置`x` 的最少跳跃次数。

关键难点与解决方案：

无限搜索空间：由于可以向前和向后跳，理论上搜索可以无限进行。必须设定一个合理的上界。
“不能连续向后跳”：需要在状态中记录上一次跳跃的方向，以决定本次可选的跳跃方式。
状态定义与去重：一个位置可能被以不同的“上次跳跃方向”访问到，需要记录(位置, 上次是否向后跳)这样一个组合状态来避免重复搜索。

方案推演与核心思路

BFS 状态设计：
- 每个 BFS 节点需要包含：(当前位置 cur, 上次是否向后跳 is_back, 当前步数 step)。
- 使用一个集合visited记录已访问的(cur, is_back)状态，避免重复搜索。
搜索上界确定：
- 参考中的分析，一个常用的、安全的右边界是max(max(forbidden) + a, x) + b。更保守且普遍采用的上界是6000（根据题目数据范围，这是一个经验值，足以覆盖所有可达状态）。本文将采用6000作为上界。
BFS 过程：
- 从初始状态(0, False, 0)开始。
- 对于每个状态(cur, is_back, step)：
  - 如果cur == x，返回step。
  - 尝试向前跳到next_cur = cur + a。若位置合法、非禁止、且状态未访问，则入队，并标记(next_cur, False)为已访问。
  - 尝试向后跳到next_cur = cur - b。前提是is_back == False（上次没向后跳）、位置合法、非禁止、且状态未访问，则入队，并标记(next_cur, True)为已访问。

代码实现 (Python)

from collections import deque class Solution: def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int: """ :type forbidden: List[int] :type a: int :type b: int :type x: int :rtype: int """ if x == 0: return 0 # 将禁止列表转换为集合，便于O(1)查找 forbid_set = set(forbidden) # BFS搜索上界，6000是一个经验值，足以覆盖题目数据范围 MAX_BOUND = 6000 # 访问状态记录，使用(位置, 是否由向后跳抵达)作为键 visited = set() # 队列元素: (当前位置, 是否由向后跳抵达, 当前步数) queue = deque() queue.append((0, False, 0)) visited.add((0, False)) while queue: cur_pos, is_back, steps = queue.popleft() # 尝试向前跳 next_pos = cur_pos + a # 检查位置是否合法：未出界、非禁止点、状态未访问 if 0 <= next_pos <= MAX_BOUND and next_pos not in forbid_set and (next_pos, False) not in visited: if next_pos == x: return steps + 1 visited.add((next_pos, False)) queue.append((next_pos, False, steps + 1)) # 尝试向后跳 (前提：上一次不是向后跳) if not is_back: next_pos = cur_pos - b # 检查位置是否合法：非负、非禁止点、状态未访问 if next_pos >= 0 and next_pos not in forbid_set and (next_pos, True) not in visited: if next_pos == x: return steps + 1 visited.add((next_pos, True)) queue.append((next_pos, True, steps + 1)) # BFS队列清空仍未找到目标，说明不可达 return -1

关键点与示例分析

为什么上界是 6000？
这是一个基于题目数据范围的工程经验值。题目中a, b, x均不超过 2000，forbidden长度不超过 1000。通过分析，最坏情况下需要探索的范围不会超过max(x, max(forbidden)) + a + b再乘以一个较小的系数，6000 是一个足够大且安全的边界，可以避免无限循环，同时不会引起不必要的性能开销。

状态(位置, 是否由向后跳抵达)的重要性
考虑以下场景：从位置p通过向前跳抵达位置q，和通过向后跳抵达位置q，这两种状态是不等价的。因为后者意味着下一次移动不能向后跳，而前者可以。因此，必须区分这两种情况，否则会丢失可行解或导致错误。

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