在 Python 中寻找到达家的最小跳跃的程序

假设有一个名为forbidden的数组，其中forbidden[i]表示bug不能跳转到forbidden[i]的位置，我们也有a、b、x三个值。虫子的家在数轴上的 x 位置。它最初位于位置 0。它可以按照以下规则跳转 -

• 错误可以准确地向右跳一个位置。

• Bug 可以准确地向左跳 b 个位置。

• Bug 不能连续两次向后跳。

• Bug 不能跳转到数组中给定的任何禁止位置。

• Bug 可以向前跳出它的家，但它不能跳到以负值编号的位置。

我们必须找到 bug 到达目的地所需的最少跳跃次数。如果没有这种可能的序列，则返回 -1。

因此，如果输入类似于 forbidden = [2,3,7,9, 12], a = 4, b = 2, x = 16，那么输出将为 7，因为从 0 开始，向前跳跃 a = 4两次到达4和8，但不能跳到12，因为这是禁止的，然后在6处后退b = 2，然后跳到10、14、18，然后两次返回到16，所以有7步。

示例

让我们看看以下实现以获得更好的理解 -

def solve(forbidden, a, b, x):
   queue, forbidden = [(x,0,True)], set(forbidden)
   lim = max(max(forbidden),x)+a+b
   while queue:
      curr,jumps,is_b = queue.pop(0)
      if curr in forbidden or not 0 <= curr <= lim:
         continue
      forbidden.add(curr)
      if curr==0:
         return jumps
      if is_b:
         queue.append((curr+b,jumps+1,False))
      queue.append((curr-a,jumps+1,True))
   return -1

forbidden = [2,3,7,9, 12]
a = 4
b = 2
x = 16
print(solve(forbidden, a, b, x))

输入

[2,3,7,9, 12], 4, 2, 16

7