Pythonで石で川を渡れるかどうかを確認するプログラム

石と呼ばれるソートされた番号のリストがあり、これが横断しようとしている川の石の位置を表しているとします。川を渡るには、最後の石で終わらせなければなりません。これで、各ステップで、（k-1、k、またはk + 1）ステップ先にジャンプできます。ここで、kは最後のジャンプの距離です。川を渡れるかどうかを確認する必要があります。

したがって、入力がstones =[0、1、3、4、5、6、8、9、13]のようである場合、出力はTrueになります。これは、0から開始して、1ユニットジャンプして石に移動できるためです。 1、次に2ユニットで3になり、その後2ユニットで5になり、次に3ユニットで8になり、最後に5ユニットで13になり、これが最後の場所です。

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

• start：=A [0]、end：=Aの最後の要素
• A：=Aのすべての一意の要素のセット
• 関数check（）を定義します。これには、pos：=start、prev：=0
が必要です。
• posがendと同じ場合、
  • Trueを返す
• [prev-1、prev、prev + 1]のジャンプごとに、実行
  • ジャンプ>=1の場合、
    • next_pos：=ジャンプ+位置
    • next_posがAにあり、check（next_pos、jump）がtrueの場合、
      • Trueを返す
• Falseを返す
• メインメソッドからcheck（）を呼び出し、結果を返します

例（Python）

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

class Solution:
   def solve(self, A):
      start, end = A[0], A[-1]
      A = set(A)
      def check(pos=start, prev=0):
         if pos == end:
            return True
         for jump in [prev - 1, prev, prev + 1]:
            if jump >= 1:
               next_pos = jump + pos
               if next_pos in A and check(next_pos, jump):
                  return True
         return False
      return check()
ob = Solution()
stones = [0, 1, 3, 4, 5, 6, 8, 9, 13]
print(ob.solve(stones))

入力

[0, 1, 3, 4, 5, 6, 8, 9, 13]

出力

True