Pythonで指定された2つの長さのジャンプを行うことにより、数値に到達できるかどうかを確認します

開始位置pにいるとすると、d1およびd2ユニットの任意の方向（左または右）にジャンプできます。 pからジャンプして、位置qに到達するために必要な最小ステップ数を見つける必要があります。

したがって、入力がp =5、q =10、d1 =4、d2 =3の場合、距離4を2回使用して右にジャンプし、位置13に到達してから左にジャンプできるため、出力は3になります。 10に到達するために3ユニット。

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

• gcd_res：=d1とd2のgcd
• （p --q）がgcd_resで割り切れない場合、
  • 戻り値-1
• que：=1つの両端キューを定義する
• 訪問：=新しいセット
• ペア（p、0）をキューに挿入します
• pを訪問済みとしてマーク
• que> 0のサイズがゼロ以外の場合、do
  • （point、step）：=キューの最前線の要素をキューから削除します
  • ポイントがqと同じ場合、
    • リターンステップ
  • ポイント+d1にアクセスしない場合は、
    • ペア（ポイント+ d1、ステップ+ 1）をqueに挿入します
    • 訪問済みとしてマーク（ポイント+ d1）
  • 訪問されていないポイント+d2がゼロ以外の場合、
    • ペア（ポイント+ d2、ステップ+ 1）をqueに挿入します
    • 訪問済みとしてマーク（ポイント+ d2）
  • 訪問されていないポイント-d1がゼロ以外の場合、
    • ペア（ポイント-d1、ステップ+ 1）をqueに挿入します
    • 訪問済みとしてマーク（ポイント-d1）
  • 訪問されていないポイント-d2がゼロ以外の場合、
    • ペア（ポイント-d2、ステップ+ 1）をqueに挿入します
    • 訪問済みとしてマーク（ポイント-d2）

例

理解を深めるために、次の実装を見てみましょう-

from math import gcd
from collections import deque
def solve(p, d1, d2, q):
   gcd_res = gcd(d1, d2)
   if (p - q) % gcd_res != 0:
      return -1
   que = deque()
   visited = set()
   que.appendleft([p, 0])
   visited.add(p)
   while len(que) > 0:
      pair = que.pop()
      point, step = pair[0], pair[1]
      if point == q:
         return step
      if point + d1 not in visited:
         que.appendleft([(point + d1), step + 1])
         visited.add(point + d1)
      if point + d2 not in visited:
         que.appendleft([(point + d2), step + 1])
         visited.add(point + d2)
      if point - d1 not in visited:
         que.appendleft([(point - d1), step + 1])
         visited.add(point - d1)
      if point - d2 not in visited:
         que.appendleft([(point - d2), step + 1])
         visited.add(point - d2)
p = 5
q = 10
d1 = 4
d2 = 3
print(solve(p, d1, d2, q))

入力

5, 4, 3, 10

出力

True