Python程序：计算骑士在棋盘上移动且不离开棋盘的概率

假设我们有四个值n、x、y和k。其中n表示n x n的棋盘，坐标(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) in moves：
    • 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))

输入

8, 1, 1, 1

输出

0

更新于：2020年11月19日

浏览量：126

开启您的职业生涯

完成课程获得认证

开始学习
广告