1654. 到家的最少跳跃次数

题目

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

跳蚤跳跃的规则如下：

它可以 往前 跳恰好 a 个位置（即往右跳）。
它可以 往后 跳恰好 b 个位置（即往左跳）。
它不能 连续 往后跳 2 次。
它不能跳到任何 forbidden 数组中的位置。
跳蚤可以往前跳 超过 它的家的位置，但是它 不能跳到负整数 的位置。

给你一个整数数组 forbidden ，其中 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 不在 forbidden 中。

思路

想着今天的每日一题有点啃不动（困难周三啊，每个周三都好难…），做一个稍微简单一点的，跳跃系列做完了，这个也是跳跃，结果并不简单…

一看这个题以为挺简单，一个就好了，结果写着写着发现不对，最远的跳跃边界不好确定，以为是#card=math&code=x%20%2B%20Math.max%28a%2C%20b%29&id=Tx9hh)，结果不对。实际是#card=math&code=max%28f%2Ba%2Bb%2Cx%2Bb%29&id=qk6lF)，其中是数组的最大值，大佬给出了证明看 这里。

另外一个问题是，卡在了第个用例（太长不放了），自己输出，结果正确答案有解。然后在 这里 找到了原因。原来每个点最多可以到达两次，向前向后各最多一次，改为二维就好了。

代码

class Solution {
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        int step = 0;
        // 数组第一位表示到达的位置，第二位表示下次是否可以向后跳，1表示可以向后跳，0表示不可以
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{0, 1});
        Set<Integer> set = new HashSet<>();
        for (int val : forbidden) {
            set.add(val);
        }
        // max(f+a+b,x+b)最大是6000
        int m = 6000;
        boolean[][] visited = new boolean[m][2];
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                int index = cur[0];
                int isBack = cur[1];
                if (index == x) {
                    return step;
                }
                if (index + a < m && !set.contains(index + a) && !visited[index + a][0]) {
                    queue.offer(new int[]{index + a, 1});
                    visited[index + a][0] = true;
                }
                if (isBack == 1 && index - b >= 0 && !set.contains(index - b) && !visited[index - b][1]) {
                    queue.offer(new int[]{index - b, 0});
                    visited[index - b][1] = true;
                }
            }
            step++;
        }
        return -1;
    }
}