โปรแกรมตรวจสอบเราสามารถข้ามแม่น้ำด้วยหินหรือไม่ใน 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 และนี่คือที่สุดท้าย

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• start :=A[0], end :=องค์ประกอบสุดท้ายของ A
• A :=ชุดขององค์ประกอบที่เป็นเอกลักษณ์ทั้งหมดของ A
• กำหนดฟังก์ชัน check() การดำเนินการนี้จะใช้เวลา pos:=start, prev:=0
• ถ้า pos เหมือนกับ end แล้ว
  • คืนค่า True
• สำหรับการกระโดดแต่ละครั้งใน [ก่อนหน้า - 1, ก่อนหน้า, ก่อนหน้า + 1] ทำ
  • ถ้ากระโดด>=1 แล้ว
    • next_pos :=กระโดด + ตำแหน่ง
    • ถ้า next_pos อยู่ใน A และตรวจสอบว่า (next_pos, jump) เป็นจริง
      • คืนค่า True
• คืนค่าเท็จ
• จากเมธอดหลัก call 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