Pythonで家にたどり着くための最小限のジャンプを見つけるプログラム

forbiddenという配列があるとします。ここで、forbidden [i]は、バグがforbidden [i]の位置にジャンプできないことを示し、a、b、xの3つの値もあります。バグの家は数直線のxの位置にあります。最初は位置0にあります。ルールに従うことでジャンプできます-

• バグは正確に右の位置にジャンプする可能性があります。

• バグは正確にb位置左にジャンプする可能性があります。

• バグは2回続けて後方にジャンプすることはできません。

• バグは、配列で指定された禁止位置にジャンプできません。

• バグはホームを超えて前方にジャンプできますが、負の値で番号付けされた位置にジャンプすることはできません。

バグが目的地に到達するために必要な最小ジャンプ数を見つける必要があります。そのような可能なシーケンスがない場合は、-1を返します。

したがって、入力が禁止=[2,3,7,9、12]、a =4、b =2、x =16のような場合、0から開始してa =4前方にジャンプするため、出力は7になります。 2回で4と8に到達しますが、これは禁止されているため12にジャンプできません。次に、6でb =2に戻り、10、14、18にジャンプし、次に2に戻って16に到達するため、7つのステップがあります。

これを解決するには、次の手順に従います-

• queue：=タプル（x、0、True）を含むキュー、禁止：=新しいセットと禁止リストからの要素の挿入

• lim：=a + b +（xの最大値と禁止セットの最大値）

• キューが空でないときに、実行します

  • （curr、jumps、is_b）：=キューから最初の要素をキューから削除します

  • currが禁止されている場合、または（0 <=curr <=lim）がfalseの場合、

    • 次のイテレーションに行く

  • 禁止にcurrを挿入します

  • currが0と同じ場合、

    • リターンジャンプ

  • is_bがtrueの場合、

    • （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