โปรแกรมหาเปอร์เซ็นต์โอกาสที่ม้าจะอยู่ในกระดานหลังเดิน k ขั้นใน Python

กำหนด n, x, y, k กระดานหมากรุก n x n ม้าอยู่ที่ (x,y) เดินสุ่ม 8 ทิศทาง k ขั้น หาเปอร์เซ็นต์โอกาส (ปัดจำนวนเต็ม) ที่ม้าอยู่ในกระดานหลัง k ขั้น หากออกนอกแล้วไม่กลับเข้ามา

ตัวอย่าง: n=8, x=1, y=1, k=1 ผลลัพธ์ 50% (4 ใน 8 ทิศทางอยู่ในกระดาน)

ขั้นตอนการแก้ปัญหา

1. รายการ 8 ทิศทางของม้า
2. ฟังก์ชัน dfs(x, y, k):
   • ถ้านอกกระดาน: คืน 0
   • ถ้า k == 0: คืน 1
   • คืน sum(dfs(x+dx, y+dy, k-1)/8 for dx,dy in moves)
3. คืน int(dfs(x,y,k) * 100)

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

moves = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]

class Solution:
    def solve(self, n, x, y, k):
        def dfs(x, y, k):
            if x < 0 or y < 0 or x >= n or y >= n:
                return 0
            if k == 0:
                return 1
            return sum(dfs(x + dx, y + dy, k - 1) / 8 for dx, dy in moves)
        return int(dfs(x, y, k) * 100)

ob = Solution()
n = 8
x = 1
y = 1
k = 1
print(ob.solve(n, x, y, k))

อินพุต

8, 1, 1, 1

เอาต์พุต

0