Python程序：查找到达目的地的最小跳跃次数

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

  • 虫子可以向右精确跳跃a个位置。

  • 虫子可以向左精确跳跃b个位置。

  • 虫子不能连续两次向后跳。

  • 虫子不能跳到数组中给出的任何禁止位置。

  • 虫子可以向前跳跃超过它的家，但它不能跳到负数编号的位置。

我们必须找到虫子到达目的地的最小跳跃次数。如果没有这样的可能序列，则返回-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和forbidden集合的最大值中的最大值)

  • 当queue不为空时，执行以下操作

    • (curr,jumps,is_b) := 从queue中获取第一个元素并将其从queue中移除

    • 如果curr在forbidden中或(0 <= curr <= lim)为假，则

      • 进入下一个迭代

    • 将curr插入forbidden

    • 如果curr与0相同，则

      • 返回jumps

    • 如果is_b为真，则

      • 将(curr+b,jumps+1,False)插入queue

    • 将(curr-a,jumps+1,True)插入queue

  • 返回-1

示例

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

Open Compiler
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

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

7

更新时间: 2021年10月6日

397 次查看

开启你的 职业生涯

完成课程获得认证

立即开始
广告