Medium

题目描述

有一只虫子的家在 x 轴上的位置 x 处。虫子从位置 0 出发，需要到达家的位置。

虫子的跳跃规则如下：

  • 它可以向前跳跃 a 个位置（向右）
  • 它可以向后跳跃 b 个位置（向左）
  • 它不能连续向后跳跃两次
  • 它不能跳跃到任何禁止的位置

虫子可以跳跃到超过家的位置，但是不能跳跃到负数位置。

给定一个整数数组 forbidden，其中 forbidden[i] 表示虫子不能跳跃到位置 forbidden[i]，以及整数 a、b 和 x，返回虫子到达家所需的最少跳跃次数。如果虫子无法通过一系列跳跃到达位置 x，则返回 -1。

示例 1：

输入：forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
输出：3
解释：3 次向前跳跃 (0 -> 3 -> 6 -> 9) 可以让虫子到家。

示例 2：

输入：forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
输出：-1

示例 3：

输入：forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
输出：2
解释：一次向前跳跃 (0 -> 16)，然后一次向后跳跃 (16 -> 7) 可以让虫子到家。

约束条件：

  • 1 <= forbidden.length <= 1000
  • 1 <= a, b, forbidden[i] <= 2000
  • 0 <= x <= 2000
  • forbidden 中的所有元素都是不同的
  • 位置 x 不在禁止位置中

解题思路

这是一道经典的 BFS（广度优先搜索）问题。关键在于如何处理状态转移和约束条件。

核心思路：

  1. 将每个位置看作图中的节点，跳跃看作边，问题转化为求最短路径
  2. 状态定义：需要记录当前位置和上一步是否为向后跳跃（因为不能连续向后跳）
  3. 使用 BFS 保证找到的第一条路径就是最短路径

关键点分析：

  • 状态表示：(position, canJumpBack) 其中 canJumpBack 表示当前是否可以向后跳
  • 状态转移：从每个状态可以向前跳 a 步，如果 canJumpBack 为 true 还可以向后跳 b 步
  • 边界处理：不能跳到负数位置，不能跳到禁止位置
  • 搜索上界：理论上虫子可能需要跳得很远再折返，上界设为 max(x, max(forbidden)) + a + b

算法流程：

  1. 将禁止位置存入哈希集合便于快速查询
  2. 使用队列进行 BFS，初始状态为 (0, true)
  3. 对每个状态尝试所有可能的跳跃，将新状态加入队列
  4. 第一次到达目标位置时返回跳跃次数

代码实现

class Solution {
public:
    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        unordered_set<int> forbiddenSet(forbidden.begin(), forbidden.end());
        
        // 设置搜索上界
        int upper = max(x, *max_element(forbidden.begin(), forbidden.end())) + a + b;
        
        // visited[pos][canBack] 表示位置pos且是否能向后跳的状态是否访问过
        vector<vector<bool>> visited(upper + 1, vector<bool>(2, false));
        
        queue<tuple<int, int, bool>> q; // (position, steps, canJumpBack)
        q.push({0, 0, true});
        visited[0][1] = true;
        
        while (!q.empty()) {
            auto [pos, steps, canBack] = q.front();
            q.pop();
            
            if (pos == x) return steps;
            
            // 向前跳
            int nextPos = pos + a;
            if (nextPos <= upper && forbiddenSet.find(nextPos) == forbiddenSet.end() 
                && !visited[nextPos][1]) {
                visited[nextPos][1] = true;
                q.push({nextPos, steps + 1, true});
            }
            
            // 向后跳（如果可以）
            if (canBack) {
                nextPos = pos - b;
                if (nextPos >= 0 && forbiddenSet.find(nextPos) == forbiddenSet.end() 
                    && !visited[nextPos][0]) {
                    visited[nextPos][0] = true;
                    q.push({nextPos, steps + 1, false});
                }
            }
        }
        
        return -1;
    }
};

class Solution:
    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
        forbidden_set = set(forbidden)
        
        # 设置搜索上界
        upper = max(x, max(forbidden)) + a + b
        
        # visited[pos][can_back] 表示位置pos且是否能向后跳的状态是否访问过
        visited = set()
        
        from collections import deque
        queue = deque([(0, 0, True)])  # (position, steps, can_jump_back)
        visited.add((0, True))
        
        while queue:
            pos, steps, can_back = queue.popleft()
            
            if pos == x:
                return steps
            
            # 向前跳
            next_pos = pos + a
            if next_pos <= upper and next_pos not in forbidden_set and (next_pos, True) not in visited:
                visited.add((next_pos, True))
                queue.append((next_pos, steps + 1, True))
            
            # 向后跳（如果可以）
            if can_back:
                next_pos = pos - b
                if next_pos >= 0 and next_pos not in forbidden_set and (next_pos, False) not in visited:
                    visited.add((next_pos, False))
                    queue.append((next_pos, steps + 1, False))
        
        return -1

public class Solution {
    public int MinimumJumps(int[] forbidden, int a, int b, int x) {
        var forbiddenSet = new HashSet<int>(forbidden);
        
        // 设置搜索上界
        int upper = Math.Max(x, forbidden.Max()) + a + b;
        
        // visited[pos, canBack] 表示位置pos且是否能向后跳的状态是否访问过
        bool[,] visited = new bool[upper + 1, 2];
        
        var queue = new Queue<(int pos, int steps, bool canBack)>();
        queue.Enqueue((0, 0, true));
        visited[0, 1] = true;
        
        while (queue.Count > 0) {
            var (pos, steps, canBack) = queue.Dequeue();
            
            if (pos == x) return steps;
            
            // 向前跳
            int nextPos = pos + a;
            if (nextPos <= upper && !forbiddenSet.Contains(nextPos) && !visited[nextPos, 1]) {
                visited[nextPos, 1] = true;
                queue.Enqueue((nextPos, steps + 1, true));
            }
            
            // 向后跳（如果可以）
            if (canBack) {
                nextPos = pos - b;
                if (nextPos >= 0 && !forbiddenSet.Contains(nextPos) && !visited[nextPos, 0]) {
                    visited[nextPos, 0] = true;
                    queue.Enqueue((nextPos, steps + 1, false));
                }
            }
        }
        
        return -1;
    }
}

var minimumJumps = function(forbidden, a, b, x) {
    const forbiddenSet = new Set(forbidden);
    const visited = new Set();
    const queue = [[0, 0, false]]; // [position, jumps, justBackward]
    const maxPos = Math.max(x, Math.max(...forbidden)) + a + b;
    
    while (queue.length > 0) {
        const [pos, jumps, justBackward] = queue.shift();
        
        if (pos === x) return jumps;
        
        const stateKey = `${pos},${justBackward}`;
        if (visited.has(stateKey)) continue;
        visited.add(stateKey);
        
        // Jump forward
        const forwardPos = pos + a;
        if (forwardPos <= maxPos && !forbiddenSet.has(forwardPos)) {
            queue.push([forwardPos, jumps + 1, false]);
        }
        
        // Jump backward (only if not just jumped backward and position > 0)
        if (!justBackward) {
            const backwardPos = pos - b;
            if (backwardPos > 0 && !forbiddenSet.has(backwardPos)) {
                queue.push([backwardPos, jumps + 1, true]);
            }
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(max(x, max(forbidden)) + a + b)
空间复杂度O(max(x, max(forbidden)) + a + b)

解释：

  • 时间复杂度：最坏情况下需要访问所有可能的状态，每个位置有两种状态（能否向后跳），搜索范围为上界值
  • 空间复杂度：主要由 visited 数组和队列占用，与搜索范围成正比

相关题目