用 Python 编写程序，找出骑士可以移动而不离开棋盘的位置百分比

pythonserver side programmingprogramming

假设我们有四个值 n、x、y 和 k。这里 n 表示一个 n x n 棋盘，x、y 坐标表示骑士位于 (x, y)。骑士必须精确走 k 步，每一步都可以随机均匀地向 8 个方向中的任何一个移动。我们必须找出骑士在走 k 步后留在棋盘上的百分比概率(最接近的整数)。我们必须遵循一个条件，即一旦离开棋盘，就不能再进入棋盘。

因此，如果输入为 n = 8、(x = 0, y = 0)、k = 1，则输出将为 50，因为这里有 8x8 棋盘，骑士的初始位置为 (1, 1)。它可以走 k = 1 步。迈出一步，它只会在 8 个位置中的 4 个位置位于棋盘内，而在其他位置位于棋盘外。所以是 50%。

为了解决这个问题，我们将遵循以下步骤 −

制作一个移动列表 [(1, 2) ,(1, -2) ,(-1, 2) ,(-1, -2) ,(2, 1) ,(2, -1) ,(-2, 1) ,(-2, -1) ]
定义一个函数 dfs() 。这将需要 x、y、k
如果 (x, y) 不在棋盘范围内，则
- 返回 0
如果 k 与 0 相同，则
- 返回 1
s = 空列表
对于所有移动 (dx, dy) 中的移动 −
- x = dfs(x + dx, y + dy, k - 1) / 8
- 将 x 插入 s
返回 s 中元素的总和
从主方法执行以下操作 −
返回 (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))