Chương trình tìm phần trăm khả năng mã ngựa không rời bàn cờ sau k bước trong Python

Mô tả bài toán

Cho bàn cờ n x n, mã ngựa tại (x,y), phải đi đúng k bước (mỗi bước chọn ngẫu nhiên 8 hướng). Tìm phần trăm (làm tròn số nguyên) mã ngựa vẫn còn trong bàn cờ sau k bước. Điều kiện: một khi rời bàn cờ không thể quay lại.

Ví dụ: n=8, (x=0,y=0), k=1 → đầu ra 50 (4/8 bước vẫn trong bàn cờ).

Giải thuật (Đệ quy + Memoization / Xác suất)

1. Danh sách 8 nước đi của mã: (±1,±2), (±2,±1).
2. Định nghĩa dfs(x, y, k):
   • Nếu ngoài bàn cờ: trả về 0.
   • Nếu k == 0: trả về 1.
   • Trả về trung bình xác suất của 8 nước đi: sum(dfs(x+dx, y+dy, k-1) / 8).
3. Kết quả: int(dfs(x, y, k) * 100).

Ví dụ mã Python

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

Đầu vào

8, 1, 1, 1

Đầu ra

0