在Python中查找到达家的最小跳数程序

在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,因为这是被禁止的,然后向后退b = 2个位置到6,然后跳到10、14、18,然后再向后跳两个位置到达16,共需要7个步骤。

为了解决这个问题,我们将采取以下步骤:

  • 队列:=带有元组(x,0,True)的队列,forbidden:=新的集合并插入来自禁止列表的元素

  • lim:=a+b+(x和禁止集合的最大值)

  • while队列不为空,执行以下操作

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

    • 如果curr在forbidden之中或(0<=curr<=lim)不成立,则执行以下操作

      • 进入下一次循环
    • 将curr插入forbidden

    • 如果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))

输入

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

输出

7

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程