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

示例

讓我們看看以下實現以獲得更好的理解：

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

更新時間: 2021年10月6日

397 次檢視

開啟你的 職業生涯

完成課程獲得認證

立即開始
廣告