【每日一题Day310】LC1654到家的最少跳跃次数 | BFS

到家的最少跳跃次数【LC1654】

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

跳蚤跳跃的规则如下：

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

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

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

• 思路：最短路问题，BFS

  • **BFS：**寻找最少跳跃次数，所以可以使用最短路径Dijkstra 算法，通过BFS实现，队列元素需要存储当前跳跃次数以及当前位置；

  • **记录状态：**由于跳跃时连续向前次数不受限制，但是不能连续向后跳两次，因此跳跃时还需要记录前一跳跃的状态为向后还是向前；

    • 如果前一状态为向前，那么本次可以向前也可以向后
    • 如果前一状态为向后，那么本次只可以向前

  • 判断是否可以访问：

    • 首先判断最远右边界，由于向前跳跃次数不受限制，避免超时，需要寻找最远右边界【重点】
    • 当前位置不在forbidden数组中
    • 之前没有访问过该状态【位置+方向】

  • 寻找最远右边界：

    • 如果$a\ge b$，那么最远右边界为$x+b$，在大于$x+b$的位置不可能到达$x$。

    • 如果$a<b$，那么可以先向前跳再向后跳逐步接近目标位置$x$，最远右边界为$max(f+a+b,x)$，其中$f$为$max(forbidden)$证明略。

      感性认知：对于任何一条路径，若它包含了超过$max(f+a+b,x)$的点，总能通过变换找到所有点都在$max(f+a+b,x)$内的路径，且这条路径与原路径跳跃次数相同，对于该问题，这两条路径是等价的，所以只需考虑$max(f+a+b,x)$内的路径即可

• 实现

  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;}
  }