688. Knight Probability in Chessboard-骑士在棋盘上的概率

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

Python:

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        dp = [[[0] * n for i in range(n)] for j in range(k+1) ]
        for s in range(k+1):
            for i in range(n):
                for j in range(n):
                        if s == 0:
                            dp[s][i][j] = 1
                        else:
                            d = [(2, 1), (2, -1), (-2, 1), (-2, -1), (-1, 2), (1, -2), (1, 2), (-1, -2)]
                            for item in d:
                                x = i + item[0]
                                y = j + item[1]
                                if 0 <= x < n and 0 <= y < n:
                                    dp[s][i][j] += dp[s-1][x][y]/8
        return dp[k][row][column]

Java:

class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        double[][][] dp = new double[k+1][n][n];

        for(int s = 0; s < k+1; s++)
        {
            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < n; j++)
                {
                    if(s == 0)
                        dp[s][i][j] = 1;
                    else
                    {
                        int[][] d = {{-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {-2, -1}, {-2, 1}, {2, -1}, {2, 1}};           
                        int x;
                        int y;
                        for(int[] t: d)
                        {
                            x = i + t[0];
                            y = j + t[1];
                            if(x >= 0 && x < n && y >= 0 && y < n)
                            {
                                dp[s][i][j] += dp[s-1][x][y]/8;
                            }
                        }
                    }
                }
            }
        }
        return dp[k][row][column];

    }
}