题目简介

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

解题思路

根据题目描述，可以先遍历一遍 forbidden 数组，将不符合跳跃规则的位置都记录下来，以备后面检查。然后根据跳跃规则和跳蚤家的位置 x，尝试计算出从 0 开始跳跃的最小次数。具体思路如下：
遍历 forbidden 数组，将不符合跳跃规则的位置记录下来。
遍历 forbidden 数组，对于每个不符合跳跃规则的位置，将它向前推进的距离记录下来。
遍历 forbidden 数组，对于每个位置，判断它是否符合跳跃规则。如果符合跳跃规则，则可以计算出跳蚤到达它的最小次数。如果不符合跳跃规则，则不需要计算它的跳跃次数。
将不符合跳跃规则的位置向前推进的距离和跳蚤到达它的最小次数作为答案返回。

代码示例

class Solution:
    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:

        if x==0:  return 0
        if x%math.gcd(a,b): return -1

        fb = set(forbidden)
        que = {(0,1)}
        visited = {(0,1)}
        step = 1
        mx = max(max(fb)+a+b,x+b)
        
        while que:
            que1 = set()
            for pos,back in que:
                pos1 = pos+a
                pos2 = pos-b
                if pos1==x or (back==0 and pos2==x): return step
                if pos1<=mx and pos1 not in fb and (pos1,0) not in visited:
                    visited.add((pos1,0))
                    que1.add((pos1,0))
                if back==0 and pos2>=0 and pos2 not in fb and (pos2,1) not in visited:
                    visited.add((pos2,1))
                    que1.add((pos2,1))
            que = que1
            step+=1
        return -1