用Python程序检查我们是否可以用石头过河

假设我们有一个称为石头的排序数字列表，它代表了我们试图穿越的河流上石头的位置。要过河，我们必须走到最后一块石头。现在，在每一步中，我们都可以向前跳（k-1，k或k + 1），其中k是最后一次跳转的距离。我们必须检查是否可以过河。

因此，如果输入就像石头= [0、1、3、4、5、6、8、9、13]，那么输出将为True，因为我们可以从0开始，然后跳1单位去石头1，然后2个单元转到3，之后将2个单元转到5，然后将3个单元转到8，最后将5个单元转到13，这是最终位置。

为了解决这个问题，我们将遵循以下步骤-

• 开始：= A [0]，结束：= A的最后一个元素

• A：= A的所有唯一元素的集合

• 定义一个功能check()。这将花费pos：=开始，上一个：= 0

• 如果pos与end相同，则

• 返回True

• 对于[prev-1，prev，prev + 1]中的每个跳转，执行

• next_pos：=jump+ pos

• 如果next_pos在A中并且check(next_pos, jump)为true，则

• 返回True

• 如果跳转> = 1，则

• 返回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