LeetCode_动态规划_中等_688.骑士在棋盘上的概率

刺骨的言语ヽ痛彻心扉 2023-10-06 23:40 34阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

![在这里插入图片描述][f488a64d03c94508bb6876e81cb0e358.png]

每次骑士要移动时，它都会随机从8种可能的移动中选择一种（即使棋子会离开棋盘），然后移动到那里。骑士继续移动，直到它走了 k 步或离开了棋盘。**返回骑士在棋盘停止移动后仍留在棋盘上的概率 。**

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

**示例 2：**  
输入: n = 1, k = 0, row = 0, column = 0  
输出: 1.00000

**提示：**  
1 <= n <= 25  
0 <= k <= 100  
0 <= row, column <= n

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/knight-probability-in-chessboard

## 2.思路 ##

（1）动态规划  
思路参考[该 LeetCode 用户题解][LeetCode]。

相关题目：  
[LeetCode\_模拟\_中等\_2596.检查骑士巡视方案][LeetCode_2596.]

## 3.代码实现（Java） ##

//思路1————动态规划
    class Solution {
        
        public double knightProbability(int n, int k, int row, int column) {
        
            //定义 8 个方向
            int[][] dirs = {
        {
        -1, -2}, {
        -2, -1}, {
        -1, 2}, {
        -2, 1}, {
        1, 2}, {
        2, 1}, {
        1, -2}, {
        2, -1}};
            // dp[i][j][p] 为从位置 (i, j) 出发，使用步数不超过 p 步，最后仍在棋盘内的概率
            double[][][] dp = new double[n][n][k + 1];
            for (int i = 0; i < n; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    dp[i][j][0] = 1;
                }
            }
            for (int p = 1; p <= k; p++) {
        
                for (int i = 0; i < n; i++) {
        
                    for (int j = 0; j < n; j++) {
        
                        for (int[] dir : dirs) {
        
                            //下一次移动到的坐标
                            int nextX = i + dir[0];
                            int nextY = j + dir[1];
                            if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n) {
        
                                //下一次移动到的坐标仍在棋盘内
                                dp[i][j][p] += dp[nextX][nextY][p - 1] / 8;
                            }                   
                        }
                    }
                }
            }
            return dp[row][column][k];
        }
    }

[f488a64d03c94508bb6876e81cb0e358.png]: https://img-blog.csdnimg.cn/f488a64d03c94508bb6876e81cb0e358.png
[LeetCode]: https://leetcode.cn/problems/knight-probability-in-chessboard/solution/gong-shui-san-xie-jian-dan-qu-jian-dp-yu-st8l/
[LeetCode_2596.]: https://blog.csdn.net/weixin_43004044/article/details/132845510