688. 骑士在棋盘上的概率

Difficulty

Medium

Tags

DFS

回溯

URL

https://leetcode.cn/problems/knight-probability-in-chessboard/

Star

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

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

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

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

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

示例 1：


输入: n = 3, k = 2, row = 0, column = 0
输出: 0.0625
解释: 有两步(到(1,2)，(2,1))可以让骑士留在棋盘上。
在每一个位置上，也有两种移动可以让骑士留在棋盘上。
骑士留在棋盘上的总概率是0.0625。

示例 2：


输入: n = 1, k = 0, row = 0, column = 0
输出: 1.00000

提示:

1 <= n <= 25

0 <= k <= 100

0 <= row, column <= n

通过次数32,808提交次数56,307

法1 记忆化搜索

思路

开始思路参考花花酱 LeetCode 688. Knight Probability in Chessboard - 刷题找工作 EP79 - YouTube

计算出从当前位置出发走 k 步之后依旧不会走出边界的走法，假设总共有 t 种走法，那么最后的答案就是 res = t / (8 ** k)，因为每一种走法的概率为 1/8**k。

所以现在问题转化为了从起点出发经过 k 步之后不出边界的走法，其等于下一步可走的 8 个位置上走 k-1步不出边界的走法总和，这个时候就看得出如何拆分当前问题了，然后采用递归实现如下。


class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        return self.dfs(n, row, column, k) / 8 **k
    @cache
    def dfs(self, n, r, c, k):
        """计算从 [r, c] 出发，走 k步依旧不出边界的走法
        """
        if r < 0 or c < 0 or r >= n or c >= n:
            return 0
        if k == 0:
            return 1
        # 遍历 8 个方向
        res = 0
        for d in [[-1,-2], [-2, -1], [-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2]]:
            res += self.dfs(n, r+d[0], c+d[1], k-1)

        return res

上述的代码的记忆化是通过 @cache 来实现的，倘若手写记忆化，那么观察参数可知，有三个参数是可变的，因此用三维数组来记录遍历中间值，代码如下：


class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        memo = [[[0]*(k+1) for _ in range(n)] for _ in range(n)]

        return self.dfs(n, row, column, k, memo) / 8 **k

    def dfs(self, n, r, c, k, memo):
        """计算从 [r, c] 出发，走 k步依旧不出边界的走法
        """
        if r < 0 or c < 0 or r >= n or c >= n:
            return 0
        if k == 0:
            return 1

        if memo[r][c][k] != 0:
            return memo[r][c][k]

        # 遍历 8 个方向
        res = 0
        for d in [[-1,-2], [-2, -1], [-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2]]:
            res += self.dfs(n, r+d[0], c+d[1], k-1, memo)

        memo[r][c][k] = res
        return res