用 Python 编写程序，查找到达家的最少跳跃次数

pythonserver side programmingprogramming更新于 2025/11/30 13:32:17

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

Bug 可以向右精确跳跃 a 个位置。
Bug 可以向左精确跳跃 b 个位置。
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 个步骤。

为了解决这个问题，我们将遵循以下步骤 −

queue := 带有元组 (x,0,True) 的队列，forbidden := 一个新集合并从 forbidden 列表中插入元素
lim := a + b + (x 的最大值和最大值禁止集)
当队列不为空时，执行
- (curr,jumps,is_b) := 队列中的第一个元素并将其从队列中删除
- 如果 curr 处于禁止状态或 (0 <= curr <= lim) 为假，则
  - 进行下一次迭代
- 将 curr 插入到禁止状态
- 如果 curr 与 0 相同，则
  - 返回 jumps
- 如果 is_b 为真，则
  - 插入(curr+b,jumps+1,False) 放入队列
- 将 (curr-a,jumps+1,True) 插入队列
返回 -1

示例

让我们看看下面的实现以便更好地理解 −

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))