Chương trình kiểm tra chúng ta có thể vượt sông bằng đá hay không bằng Python

Giả sử chúng ta có một danh sách các số được sắp xếp được gọi là đá và đây là vị trí của các viên đá trên một con sông mà chúng ta đang cố băng qua. Để qua sông, chúng ta phải hoàn thành ở viên đá cuối cùng. Bây giờ trong mỗi bước, chúng ta có thể nhảy trước (k - 1, k hoặc k + 1) bước với k là khoảng cách của bước nhảy cuối cùng. Chúng tôi phải kiểm tra xem chúng tôi có thể qua sông hay không.

Vì vậy, nếu đầu vào giống như đá =[0, 1, 3, 4, 5, 6, 8, 9, 13], thì đầu ra sẽ là Đúng, vì chúng ta có thể bắt đầu từ 0, sau đó nhảy 1 đơn vị để đi đá 1, sau đó 2 đơn vị để đi 3, sau đó 2 đơn vị đến 5, sau đó 3 đơn vị để đi 8, và cuối cùng là 5 đơn vị để đi 13, và đây là vị trí cuối cùng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• start:=A [0], end:=phần tử cuối cùng của A
• A:=tập hợp tất cả các phần tử duy nhất của A
• Xác định một kiểm tra hàm (). Điều này sẽ lấy pos:=start, pres:=0
• nếu pos giống như end, thì
  • trả về True
• đối với mỗi bước nhảy trong [trước - 1, trước, trước + 1], hãy thực hiện
  • nếu jump> =1, thì
    • next_pos:=jump + pos
    • nếu next_pos ở A và kiểm tra (next_pos, jump) là đúng, thì
      • trả về True
• trả về Sai
• Từ phương thức chính, hãy gọi check () và trả về kết quả

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

True