目标
在一个 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 - 1
思路
在 n x n 棋盘上的 (row, column) 位置上有一个骑士（坐标从 0 开始），求它朝 8 个方向任意走 k 次还停留在棋盘上的概率是多少。所谓的 8 个方向类似中国象棋中的马走 日，不过没有蹩马腿的限制。
定义 dp[i][j][k] 表示当前在 (i, j) 走 k 步后最终在棋盘上的概率。初始 dp[i][j][0] = 1，dp[i][j][k] = Σdp[.][.][k - 1] / 8，最终的结果为 dp[row][column][k]。
代码
/**
* @date 2024-12-07 20:48
*/
public class KnightProbability688 {
public double knightProbability(int n, int k, int row, int column) {
int[][] direction = new int[][]{{-1, -2}, {-2, -1}, {-1, 2}, {-2, 1}, {1, 2}, {2, 1}, {1, -2}, {2, -1}};
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.0;
}
}
for (int step = 1; step <= k; step++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int d = 0; d < 8; d++) {
int dx = direction[d][0];
int dy = direction[d][1];
int x = i + dx;
int y = j + dy;
if (x >= 0 && x < n && y >= 0 && y < n) {
dp[i][j][step] += dp[x][y][step - 1];
}
}
dp[i][j][step] /= 8;
}
}
}
return dp[row][column][k];
}
}
性能
