到家的最少跳跃次数【LC1654】
有一只跳蚤的家在数轴上的位置
x处。请你帮助它从位置0出发，到达它的家。跳蚤跳跃的规则如下：
- 它可以 往前 跳恰好
a个位置（即往右跳）。- 它可以 往后 跳恰好
b个位置（即往左跳）。- 它不能 连续 往后跳
2次。- 它不能跳到任何
forbidden数组中的位置。跳蚤可以往前跳 超过 它的家的位置，但是它 不能跳到负整数 的位置。
给你一个整数数组
forbidden，其中forbidden[i]是跳蚤不能跳到的位置，同时给你整数a，b和x，请你返回跳蚤到家的最少跳跃次数。如果没有恰好到达x的可行方案，请你返回-1。
思路：最短路问题，BFS
- **BFS：**寻找最少跳跃次数，所以可以使用最短路径Dijkstra 算法，通过BFS实现，队列元素需要存储当前跳跃次数以及当前位置；
- **记录状态：**由于跳跃时连续向前次数不受限制，但是不能连续向后跳两次，因此跳跃时还需要记录前一跳跃的状态为向后还是向前；
- 如果前一状态为向前，那么本次可以向前也可以向后
- 如果前一状态为向后，那么本次只可以向前
- 判断是否可以访问：
- 首先判断最远右边界，由于向前跳跃次数不受限制，避免超时，需要寻找最远右边界【重点】
- 当前位置不在
forbidden数组中 - 之前没有访问过该状态【位置+方向】
class Solution { public int minimumJumps(int[] forbidden, int a, int b, int x) { Set<Integer> vis = new HashSet<>(); Deque<int[]> pq = new LinkedList<>();// 跳跃次数、当前位置、连续向后跳次数 int max = 0; for (int f : forbidden){ vis.add(f); max = Math.max(max, f); } if (a > b){ max = x + b; }else{ max = Math.max(max + a + b, x); } boolean[][] flag = new boolean[max + 1][2];// 向前 向后一次 flag[0][0] = true; pq.addLast(new int[]{0, 0, 0}); while (!pq.isEmpty()){ int[] node = pq.pollFirst(); if (node[1] == x) return node[0]; // 向前 int forward = node[1] + a; if (forward <= max && !vis.contains(forward) && !flag[forward][0]){ flag[forward][0] = true; pq.addLast(new int[]{node[0] + 1, forward, 0}); } // 向后 int backward = node[1] - b; if (node[2] != 1 && backward >= 0 && !vis.contains(backward) && !flag[backward][1]){ flag[backward][1] = true; pq.addLast(new int[]{node[0] + 1, backward, 1}); } } return -1; } }
