在Python中寻找骑士可以移动但不离开棋盘的位置的百分比

假设我们有四个值 n、x、y 和 k。这里 n 表示 n x n 的棋盘，x，y 坐标表示一个骑士放置在 (x，y)。骑士必须恰好取 k 步，每一步都可以随机均匀地移动 8 个方向之一。我们必须找到骑士在取 k 步后仍然位于棋盘上的概率机会（最接近的整数）。我们必须遵循一个条件，即一旦它离开就不能再进入棋盘。

因此，如果输入是 n = 8，(x = 0，y = 0)，k = 1，则输出将为 50，因为这里我们有 8×8 的棋盘，骑士的初始位置为 (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）)到最近的整数

让我们来看下面的实现，以获得更好的理解 –

更多Python相关文章，请阅读：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))