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
| // @Title: 骑士在棋盘上的概率 (Knight Probability in Chessboard)
// @Author: 15816537946@163.com
// @Date: 2022-02-17 00:21:09
// @Runtime: 4 ms
// @Memory: 3.6 MB
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]
}
|