在Python中检查我们是否可以通过石头或无法通过河流

假设我们有一个名为stones的已排序数字列表，它表示我们试图跨越的河流上的石头的位置。要穿过河，我们必须完成最后一块石头。现在，在每一步中，我们可以向前跳跃（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：=跳跃+ 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))