题目描述
在一个 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 <= 250 <= k <= 1000 <= row, column <= n - 1
解法
方法一：动态规划
我们定义 $f[h][i][j]$ 表示骑士从 $(i, j)$ 位置出发，走了 $h$ 步以后还留在棋盘上的概率。那么最终答案就是 $f[k][\textit{row}][\textit{column}]$。
当 $h=0$ 时，骑士一定在棋盘上，概率为 $1$，即 $f[0][i][j]=1$。
当 $h \gt 0$ 时，骑士在 $(i, j)$ 位置上的概率可以由其上一步的 $8$ 个位置上的概率转移得到，即：
$$
f[h][i][j] = \sum_{x, y} f[h - 1][x][y] \times \frac{1}{8}
$$
其中 $(x, y)$ 是从 $(i, j)$ 位置可以走到的 $8$ 个位置中的一个。
最终答案即为 $f[k][\textit{row}][\textit{column}]$。
时间复杂度 $O(k \times n^2)$，空间复杂度 $O(k \times n^2)$。其中 $k$ 和 $n$ 分别是给定的步数和棋盘大小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution:
def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
f = [[[0] * n for _ in range(n)] for _ in range(k + 1)]
for i in range(n):
for j in range(n):
f[0][i][j] = 1
for h in range(1, k + 1):
for i in range(n):
for j in range(n):
for a, b in pairwise((-2, -1, 2, 1, -2, 1, 2, -1, -2)):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < n:
f[h][i][j] += f[h - 1][x][y] / 8
return f[k][row][column]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution {
public double knightProbability(int n, int k, int row, int column) {
double[][][] f = new double[k + 1][n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
f[0][i][j] = 1;
}
}
int[] dirs = {-2, -1, 2, 1, -2, 1, 2, -1, -2};
for (int h = 1; h <= k; ++h) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int p = 0; p < 8; ++p) {
int x = i + dirs[p], y = j + dirs[p + 1];
if (x >= 0 && x < n && y >= 0 && y < n) {
f[h][i][j] += f[h - 1][x][y] / 8;
}
}
}
}
}
return f[k][row][column];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | class Solution {
public:
double knightProbability(int n, int k, int row, int column) {
double f[k + 1][n][n];
memset(f, 0, sizeof(f));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
f[0][i][j] = 1;
}
}
int dirs[9] = {-2, -1, 2, 1, -2, 1, 2, -1, -2};
for (int h = 1; h <= k; ++h) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int p = 0; p < 8; ++p) {
int x = i + dirs[p], y = j + dirs[p + 1];
if (x >= 0 && x < n && y >= 0 && y < n) {
f[h][i][j] += f[h - 1][x][y] / 8;
}
}
}
}
}
return f[k][row][column];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | func knightProbability(n int, k int, row int, column int) float64 {
f := make([][][]float64, k+1)
for h := range f {
f[h] = make([][]float64, n)
for i := range f[h] {
f[h][i] = make([]float64, n)
for j := range f[h][i] {
f[0][i][j] = 1
}
}
}
dirs := [9]int{-2, -1, 2, 1, -2, 1, 2, -1, -2}
for h := 1; h <= k; h++ {
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
for p := 0; p < 8; p++ {
x, y := i+dirs[p], j+dirs[p+1]
if x >= 0 && x < n && y >= 0 && y < n {
f[h][i][j] += f[h-1][x][y] / 8
}
}
}
}
}
return f[k][row][column]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | function knightProbability(n: number, k: number, row: number, column: number): number {
const f = Array.from({ length: k + 1 }, () =>
Array.from({ length: n }, () => Array(n).fill(0)),
);
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
f[0][i][j] = 1;
}
}
const dirs = [-2, -1, 2, 1, -2, 1, 2, -1, -2];
for (let h = 1; h <= k; ++h) {
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
for (let p = 0; p < 8; ++p) {
const x = i + dirs[p];
const y = j + dirs[p + 1];
if (x >= 0 && x < n && y >= 0 && y < n) {
f[h][i][j] += f[h - 1][x][y] / 8;
}
}
}
}
}
return f[k][row][column];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | impl Solution {
pub fn knight_probability(n: i32, k: i32, row: i32, column: i32) -> f64 {
let n = n as usize;
let k = k as usize;
let mut f = vec![vec![vec![0.0; n]; n]; k + 1];
for i in 0..n {
for j in 0..n {
f[0][i][j] = 1.0;
}
}
let dirs = [-2, -1, 2, 1, -2, 1, 2, -1, -2];
for h in 1..=k {
for i in 0..n {
for j in 0..n {
for p in 0..8 {
let x = i as isize + dirs[p];
let y = j as isize + dirs[p + 1];
if x >= 0 && x < n as isize && y >= 0 && y < n as isize {
let x = x as usize;
let y = y as usize;
f[h][i][j] += f[h - 1][x][y] / 8.0;
}
}
}
}
}
f[k][row as usize][column as usize]
}
}
|