骑士在棋盘上的概率

688. 骑士在棋盘上的概率

在一个 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

相似题目

出界的路径数

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: double knightProbability(int n, int k, int row, int column) { } };

javascript 解法, 执行用时: 84 ms, 内存消耗: 43.3 MB, 提交时间: 2022-12-08 11:05:26

const dirs = [[-2, -1], [-2, 1], [2, -1], [2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2]];
/**
 * @param {number} n
 * @param {number} k
 * @param {number} row
 * @param {number} column
 * @return {number}
 */
var knightProbability = function(n, k, row, column) {
    const dp = new Array(k + 1).fill(0).map(() => new Array(n).fill(0).map(() => new Array(n).fill(0)));
    for (let step = 0; step <= k; step++) {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (step === 0) {
                    dp[step][i][j] = 1;
                } else {
                    for (const dir of dirs) {
                        const ni = i + dir[0], nj = j + dir[1];
                        if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                            dp[step][i][j] += dp[step - 1][ni][nj] / 8;
                        }
                    }
                }
            }
        }
    }
    return dp[k][row][column];
};

golang 解法, 执行用时: 4 ms, 内存消耗: 3.6 MB, 提交时间: 2022-12-08 11:04:52

var dirs = []struct{ i, j int }{{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}}

func knightProbability(n, k, row, column int) float64 {
    dp := make([][][]float64, k+1)
    for step := range dp {
        dp[step] = make([][]float64, n)
        for i := 0; i < n; i++ {
            dp[step][i] = make([]float64, n)
            for j := 0; j < n; j++ {
                if step == 0 {
                    dp[step][i][j] = 1
                } else {
                    for _, d := range dirs {
                        if x, y := i+d.i, j+d.j; 0 <= x && x < n && 0 <= y && y < n {
                            dp[step][i][j] += dp[step-1][x][y] / 8
                        }
                    }
                }
            }
        }
    }
    return dp[k][row][column]
}

java 解法, 执行用时: 7 ms, 内存消耗: 40.8 MB, 提交时间: 2022-12-08 11:04:38

class Solution {
    static int[][] dirs = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}};

    public double knightProbability(int n, int k, int row, int column) {
        double[][][] dp = new double[k + 1][n][n];
        for (int step = 0; step <= k; step++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (step == 0) {
                        dp[step][i][j] = 1;
                    } else {
                        for (int[] dir : dirs) {
                            int ni = i + dir[0], nj = j + dir[1];
                            if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                                dp[step][i][j] += dp[step - 1][ni][nj] / 8;
                            }
                        }
                    }
                }
            }
        }
        return dp[k][row][column];
    }
}

python3 解法, 执行用时: 332 ms, 内存消耗: 17.7 MB, 提交时间: 2022-12-08 11:04:24

'''
定义 dp[step][i][j] 表示骑士从棋盘上的点 (i,j) 出发，走了 step 步时仍然留在棋盘上的概率
当(i,j)不在棋盘上，dp[step][i][j] = 0, 当(i,j)在棋盘上，dp[0][i][j] = 1;
'''
class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        dp = [[[0] * n for _ in range(n)] for _ in range(k + 1)]
        for step in range(k + 1):
            for i in range(n):
                for j in range(n):
                    if step == 0:
                        dp[step][i][j] = 1
                    else:
                        for di, dj in ((-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)):
                            ni, nj = i + di, j + dj
                            if 0 <= ni < n and 0 <= nj < n:
                                dp[step][i][j] += dp[step - 1][ni][nj] / 8
        return dp[k][row][column]

上一题

下一题

详情