โปรแกรมตรวจสอบว่าข้ามแม่น้ำได้ด้วยหินหรือไม่ใน Python

สมมติว่าเรามีรายการตัวเลขเรียงลำดับ stones แสดงตำแหน่งหินในแม่น้ำ ต้องข้ามไปหินสุดท้าย ในแต่ละขั้นตอน กระโดดได้ k-1, k, k+1 หน่วย โดย k คือระยะกระโดดครั้งก่อน ตรวจสอบว่าข้ามได้หรือไม่

เช่น stones = [0, 1, 3, 4, 5, 6, 8, 9, 13] ผลลัพธ์ = True เส้นทาง: 0→1 (1), 1→3 (2), 3→5 (2), 5→8 (3), 8→13 (5)

ขั้นตอนการแก้ปัญหา (DFS + Memoization)

• start := stones[0], end := stones[-1]
• stones_set := set(stones)
• ฟังก์ชัน check(pos=start, prev=0):
  • ถ้า pos == end คืน True
  • วน jump in [prev-1, prev, prev+1]:
    • ถ้า jump >= 1:
      • next_pos = pos + jump
      • ถ้า next_pos in stones_set และ check(next_pos, jump) คืน True
  • คืน False
• คืน check()

ตัวอย่างโค้ด

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