資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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
397 次檢視
