Leetcode688：骑士在棋盘上的概率

题目描述：

在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，并尝试进行 k 次移动。行和列是 从 0 开始 的，所以左上单元格是 (0,0) ，右下单元格是 (n - 1, n - 1) 。

象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。

每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。

骑士继续移动，直到它走了 k 步或离开了棋盘。

返回 骑士在棋盘停止移动后仍留在棋盘上的概率 。

代码思路：

这段代码通过递归和缓存的方法，目的是解决一个关于国际象棋中马（骑士）移动的概率问题。

具体来说，给定一个 n x n 的棋盘，一个骑士初始位于 (row, column) 位置，并且它可以移动 k 步。每一步，骑士按照国际象棋的规则随机选择一个合法的移动（即八个方向之一），包括两个水平方向各移动两格然后垂直方向移动一格，或者垂直方向各移动两格然后水平方向移动一格。问题是要求出骑士在 k 步内停留在棋盘上的概率（骑士不能走出棋盘）。

以下是代码的详细思路：

1. 定义移动方向：
   • points = [(-1, -2), (1, -2), (-1, 2), (1, 2), (-2, -1), (-2, 1), (2, -1), (2, 1)]：这个列表包含了骑士可以移动的八个方向，每个方向都是一个元组 (i, j)，表示从当前位置 (row, column) 移动到 (row+i, column+j)。
2. 使用缓存：
   • @cache：这是一个装饰器，用于缓存函数的返回值。这意味着对于相同的输入参数，函数不会重复计算，而是直接返回之前计算的结果。这大大减少了重复计算，提高了效率。
3. 递归函数 get_probability：
   • 输入参数为当前位置 (row, column) 和已经移动的步数 step。
   • 终止条件：
     • 如果当前位置在棋盘内（0 <= row < n 且 0 <= column < n），并且 k == 0（不需要再移动）或 step == k（已经移动了 k 步），则返回 1，表示骑士停留在当前位置的概率是 1。
     • 如果当前位置不在棋盘内，返回 0，表示骑士不可能停留在这个位置。
   • 递归计算：
     • 对于当前位置，骑士有八个可能的下一步位置。对每个可能的下一步位置，递归调用 get_probability 函数，计算从该下一步位置继续移动 (step+1) 步后停留在棋盘上的概率。
     • 将这八个概率相加，并除以 8（因为每一步有八种等概率的选择），得到从当前位置出发，在 k 步内停留在棋盘上的总概率。
4. 返回结果：
   • 调用 get_probability(row, column, 0)，从初始位置 (row, column) 开始，计算骑士在 k 步内停留在棋盘上的概率，并返回这个概率值。

代码实现：

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        points = [(-1, -2), (1, -2), (-1, 2), (1, 2), (-2, -1), (-2, 1), (2, -1), (2, 1)]
        @cache
        def get_probability(row: int, column: int, step: int):
            if 0<= row < n and 0<= column < n:
                if k == 0 or step == k:
                    return 1
                return sum(get_probability(row+i, column+j, step+1) for i, j in points)/8
            else:
                return 0
        return get_probability(row, column, 0)

 

原文地址：https://blog.csdn.net/m0_67598823/article/details/144335051

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！