到家的最少跳跃次数

2021-02-05

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

跳蚤跳跃的规则如下：

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

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

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

示例 1：

1
2
3

输入：forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
输出：3
解释：往前跳 3 次（0 -> 3 -> 6 -> 9），跳蚤就到家了。

示例 2：

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

示例 3：

1
2
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 不在 forbidden 中。

BFS(待填坑)

class Solution {
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        Set<Integer> forbiddenSet = new HashSet<>(forbidden.length);
        for (int i : forbidden) {
            forbiddenSet.add(i);
        }
        Queue<Step> queue = new LinkedList<>();
        queue.add(new Step(0, 0, false));
        while (!queue.isEmpty()) {
            Step step = queue.poll();
            if (step.cur == x) {
                return step.stepCount;
            }
            int forward = step.cur + a;
            // 这个6000 在lc题解里有个复杂的证明，即超出 a + b + max(x, every forbidden)是没有意义的
            if (forward <= 6000 && !forbiddenSet.contains(forward)) {
                // 前进到一个点,下一次就不要再回到这个状态了
                forbiddenSet.add(forward);
                queue.add(new Step(forward, step.stepCount + 1, false));
            }
            int back = step.cur - b;
            if (!step.back && back > 0 && !forbiddenSet.contains(back)) {
                // 后退是不能置forbbiden的，因为不能连续后退，而如果是前进到这个点的情况，则可以在此后退
                queue.add(new Step(back, step.stepCount + 1, true));
            }
        }
        return -1;
    }

    public static class Step {
        // 当前的位置
        int cur;
        // 当前的步数
        int stepCount;
        // 是否为后退到达的
        boolean back;
        Step(int c, int n, boolean b) {
            cur = c;
            stepCount = n;
            back = b;
        }
    }
}

作者：yangge-c
链接：https://leetcode-cn.com/problems/minimum-jumps-to-reach-home/solution/java-bfs-by-yangge-c/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

DFS

class Solution{
      public int minimumJumps(int[] forbidden, int a, int b, int x) {
        int max = 0;
        for (int i : forbidden) {
            max = Math.max(i, max);
        }
        max = Math.max(max, x) + a + b;
        //为什么是max+1，我也不知道为什么。。。。如果是max，会有一个用例错误
        //改为6000 也是可以的，但是可能会更耗时间
        int[] forbiddenPos = new int[max+1];
        for (int i : forbidden) {
            forbiddenPos[i] = -1;
        }
        forbiddenPos[0] = -1;
        return minimumJumpsDfs2(forbiddenPos, 0, a, b, x, false);
    }

    int minimumJumpsDfs2(int[] forbiddenPos, int crt, int a, int b, int x, boolean isBack) {
        if (crt == x) {
            return 0;
        }
        int rev = -1;
        //dfs 遍历顺序不可以改动，由于总是优先向前跳，所以当找到第一个值时，就为最小值
        if (crt + a < forbiddenPos.length && forbiddenPos[crt + a] != -1) {
            forbiddenPos[crt + a] = -1;
            rev = minimumJumpsDfs2(forbiddenPos, crt + a, a, b, x, false);
            if (rev != -1) {
                return 1 + rev;
            }
        }
        if (!isBack && crt - b >= 0 && forbiddenPos[crt - b] != -1) {
            rev = minimumJumpsDfs2(forbiddenPos, crt - b, a, b, x, true);
            if (rev != -1) {
                return 1 + rev;
            }
        }
        return rev;
    }

作者：iuy-m
链接：https://leetcode-cn.com/problems/minimum-jumps-to-reach-home/solution/java-jian-ji-dfs-by-iuy-m-mj2s/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}

关联题目