Giả sử chúng ta có bốn giá trị n, x, y và k. Ở đây n biểu thị một bàn cờ n x n và tọa độ x, y đại diện cho một quân mã được đặt tại (x, y). Hiệp sĩ phải đi chính xác k bước, tại mỗi bước nó có thể di chuyển ngẫu nhiên bất kỳ hướng nào trong 8 hướng đồng nhất. Chúng ta phải tìm tỷ lệ phần trăm cơ hội (số nguyên gần nhất) mà quân sĩ vẫn còn trong bàn cờ sau khi thực hiện k nước đi. Chúng tôi phải tuân theo một điều kiện là nó không thể vào lại bảng một khi nó rời khỏi nó.
Vì vậy, nếu đầu vào là n =8, (x =0, y =0), k =1, thì đầu ra sẽ là 50, như ở đây chúng ta có bàn cờ 8x8 và vị trí ban đầu của quân mã là (1, 1 ). Có thể mất k =1 bước. Thực hiện một bước, nó sẽ chỉ nằm bên trong bảng ở 4 trong số 8 vị trí, và sẽ nằm bên ngoài ở các vị trí khác. Vì vậy, 50%.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Lập danh sách các bước di chuyển [(1, 2), (1, -2), (- 1, 2), (- 1, -2), (2, 1), (2, -1), (-2, 1), (- 2, -1)]
- Định nghĩa một hàm dfs (). Điều này sẽ lấy x, y, k
- nếu (x, y) không nằm trong phạm vi của bảng, thì
- trả về 0
- nếu k giống 0, thì
- trả lại 1
- s =danh sách trống
- cho tất cả các nước đi (dx, dy) trong các nước đi -
- x =dfs (x + dx, y + dy, k - 1) / 8
- chèn x vào s
- trả về tổng của các phần tử trong s
- Từ phương thức chính, hãy làm như sau -
- trả về kết quả làm tròn của (dfs (x, y, k) * 100) thành số nguyên gần nhất
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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