题目簡介#
有一隻跳蚤的家在數軸上的位置 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