LEETCODE-到家的最少跳跃次数

题目描述

有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发，到达它的家。

跳蚤跳跃的规则如下：

• 它可以 往前 跳恰好 a 个位置（即往右跳）。
• 它可以 往后 跳恰好 b 个位置（即往左跳）。
• 它不能 连续 往后跳 2 次。
• 它不能跳到任何 forbidden 数组中的位置。

跳蚤可以往前跳 超过 它的家的位置，但是它 不能跳到负整数 的位置。

给你一个整数数组 forbidden ，其中 forbidden[i] 是跳蚤不能跳到的位置，同时给你整数 a， b 和 x ，请你返回跳蚤到家的最少跳跃次数。如果没有恰好到达 x 的可行方案，请你返回 -1 。

解题思路：

BFS 的基本思路是从起点开始，逐层地向外扩展，直到找到目标位置或者无法继续扩展为止。我们可以将跳蚤的位置和已经跳跃的次数作为状态进行搜索。

具体的算法如下：

1. 初始化一个队列 queue，并将起点状态 (0, 0, 1) 加入队列。其中，(0, 0) 表示跳蚤的位置和已经跳跃的次数，1 表示跳蚤上一次是否是向后跳。
2. 初始化一个集合 visited，用于记录已经访问过的状态，避免重复搜索。
3. 进入循环，直到队列为空：
   • 从队列中取出一个状态 (pos, steps, backward)。
   • 如果 pos 等于目标位置 x，返回 steps，表示找到了最少跳跃次数。
   • 将当前状态标记为已访问，即将 (pos, backward) 添加到 visited 集合中。
   • 根据跳蚤的跳跃规则，生成下一步可能的状态：
     • 如果不是连续向后跳或者当前位置向前跳的结果不在 forbidden 数组中，并且没有访问过该状态，则将该状态加入队列：(pos + a, steps + 1, 0)。
     • 如果当前位置向后跳的结果不在 forbidden 数组中，并且没有访问过该状态，则将该状态加入队列：(pos - b, steps + 1, 1)。
4. 如果循环结束时仍未找到目标位置 x，表示无法到达，返回 -1。

解题编码

 public int minimumJumps(int[] forbidden, int a, int b, int x) {
         Set<Integer> forbiddenSet = new HashSet<>();
        for (int pos : forbidden) {
            forbiddenSet.add(pos);
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 0}); // pos, steps, backward

        Set<String> visited = new HashSet<>();
        visited.add("0,false");

        while (!queue.isEmpty()) {
            int[] state = queue.poll();
            int pos = state[0];
            int steps = state[1];
            int backward = state[2];

            if (pos == x) {
                return steps;
            }

            if (visited.contains(pos + "," + backward)) {
                continue;
            }

            visited.add(pos + "," + backward);

            if (pos + a <= 6000 && !forbiddenSet.contains(pos + a) ) {
                queue.offer(new int[]{pos + a, steps + 1, 0});
            }

            if (pos - b >= 0 && !forbiddenSet.contains(pos - b)&& backward == 0) {
                queue.offer(new int[]{pos - b, steps + 1, 1});
            }
        }

        return -1;
    }

执行结果