Question

1654. 到家的最少跳跃次数

English Version

题目描述

有一只跳蚤的家在数轴上的位置 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 中。

解法

方法一：BFS

我们可以将跳蚤的位置和跳跃方向作为状态，使用 BFS 搜索最短路径。本题比较关键的地方在于确定右边界，即跳蚤最远能跳到哪里。

如果 $a \geq b$，即往前跳的距离大于往后跳的距离，那么如果跳蚤在位置大于 $x+b$ 的地方，它就不能再往前跳了，因为跳蚤不能连续往后跳两次，如果继续往前跳，那么永远无法跳到 $x$ 的位置。因此，如果 $a \geq b$，那么右边界可以是 $x+b$。

如果 $a \lt b$，即往前跳的距离小于往后跳的距离，那么如果跳蚤所在的位置减去 $b$ 超过 $2000$，此时选择往后跳，否则往前跳。因此，如果 $a \lt b$，那么右边界不超过 $6000$。

综上，我们可以将右边界设置为 $6000$。

接下来，我们使用 BFS 搜索最短路径。我们使用一个队列，初始时将跳蚤的位置和跳跃方向作为状态加入队列。每次从队列中取出一个状态，如果该状态的位置等于 $x$，那么我们就找到了一条从初始状态到达目标状态的路径，返回当前的步数即可。否则，我们将当前状态的下一个状态加入队列，下一个状态有两种情况：

• 往前跳，跳跃方向为 $1$；
• 当前跳跃方向为 $1$ 时，往后跳，跳跃方向为 $0$。

注意，我们需要判断下一个状态是否合法，即下一个状态的位置不超过右边界，且不在禁止的位置中，且未被访问过。

如果队列为空，说明无法到达目标位置，返回 $-1$。

时间复杂度 $O(M)$，空间复杂度 $O(M)$。其中 $M$ 是右边界，本题中 $M \leq 6000$。

class Solution:
  def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
    s = set(forbidden)
    q = deque([(0, 1)])
    vis = {(0, 1)}
    ans = 0
    while q:
      for _ in range(len(q)):
        i, k = q.popleft()
        if i == x:
          return ans
        nxt = [(i + a, 1)]
        if k & 1:
          nxt.append((i - b, 0))
        for j, k in nxt:
          if 0 <= j < 6000 and j not in s and (j, k) not in vis:
            q.append((j, k))
            vis.add((j, k))
      ans += 1
    return -1

class Solution {
  public int minimumJumps(int[] forbidden, int a, int b, int x) {
    Set<Integer> s = new HashSet<>();
    for (int v : forbidden) {
      s.add(v);
    }
    Deque<int[]> q = new ArrayDeque<>();
    q.offer(new int[] {0, 1});
    final int n = 6000;
    boolean[][] vis = new boolean[n][2];
    vis[0][1] = true;
    for (int ans = 0; !q.isEmpty(); ++ans) {
      for (int t = q.size(); t > 0; --t) {
        var p = q.poll();
        int i = p[0], k = p[1];
        if (i == x) {
          return ans;
        }
        List<int[]> nxt = new ArrayList<>();
        nxt.add(new int[] {i + a, 1});
        if ((k & 1) == 1) {
          nxt.add(new int[] {i - b, 0});
        }
        for (var e : nxt) {
          int j = e[0];
          k = e[1];
          if (j >= 0 && j < n && !s.contains(j) && !vis[j][k]) {
            q.offer(new int[] {j, k});
            vis[j][k] = true;
          }
        }
      }
    }
    return -1;
  }
}

class Solution {
public:
  int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
    unordered_set<int> s(forbidden.begin(), forbidden.end());
    queue<pair<int, int>> q;
    q.emplace(0, 1);
    const int n = 6000;
    bool vis[n][2];
    memset(vis, false, sizeof(vis));
    vis[0][1] = true;
    for (int ans = 0; q.size(); ++ans) {
      for (int t = q.size(); t; --t) {
        auto [i, k] = q.front();
        q.pop();
        if (i == x) {
          return ans;
        }
        vector<pair<int, int>> nxts = {{i + a, 1}};
        if (k & 1) {
          nxts.emplace_back(i - b, 0);
        }
        for (auto [j, l] : nxts) {
          if (j >= 0 && j < n && !s.count(j) && !vis[j][l]) {
            vis[j][l] = true;
            q.emplace(j, l);
          }
        }
      }
    }
    return -1;
  }
};

func minimumJumps(forbidden []int, a int, b int, x int) (ans int) {
  s := map[int]bool{}
  for _, v := range forbidden {
    s[v] = true
  }
  q := [][2]int{[2]int{0, 1}}
  const n = 6000
  vis := make([][2]bool, n)
  vis[0][1] = true
  for ; len(q) > 0; ans++ {
    for t := len(q); t > 0; t-- {
      p := q[0]
      q = q[1:]
      i, k := p[0], p[1]
      if i == x {
        return
      }
      nxt := [][2]int{[2]int{i + a, 1}}
      if k&1 == 1 {
        nxt = append(nxt, [2]int{i - b, 0})
      }
      for _, e := range nxt {
        j, l := e[0], e[1]
        if j >= 0 && j < n && !s[j] && !vis[j][l] {
          q = append(q, [2]int{j, l})
          vis[j][l] = true
        }
      }
    }
  }
  return -1
}

function minimumJumps(forbidden: number[], a: number, b: number, x: number): number {
  const s: Set<number> = new Set(forbidden);
  const q: [number, number][] = [[0, 1]];
  const n = 6000;
  const vis: boolean[][] = Array.from({ length: n }, () => [false, false]);
  vis[0][1] = true;
  for (let ans = 0; q.length; ++ans) {
    for (let t = q.length; t; --t) {
      const [i, k] = q.shift()!;
      if (i === x) {
        return ans;
      }
      const nxt: [number, number][] = [[i + a, 1]];
      if (k & 1) {
        nxt.push([i - b, 0]);
      }
      for (const [j, k] of nxt) {
        if (j >= 0 && j < n && !s.has(j) && !vis[j][k]) {
          vis[j][k] = true;
          q.push([j, k]);
        }
      }
    }
  }
  return -1;
}