-
Notifications
You must be signed in to change notification settings - Fork 1
/
KnightProbabilityInChessboard.java
74 lines (69 loc) · 2.9 KB
/
KnightProbabilityInChessboard.java
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
package com.hncboy;
/**
* @author hncboy
* @date 2022/2/17 8:58
* 688.骑士在棋盘上的概率
*
* 在一个 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
* 通过次数 11,413 提交次数 21,090
*
* 来源:力扣(LeetCode)
* 链接:https://leetcode-cn.com/problems/knight-probability-in-chessboard
* 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*/
public class KnightProbabilityInChessboard {
public static void main(String[] args) {
KnightProbabilityInChessboard k = new KnightProbabilityInChessboard();
System.out.println(k.knightProbability(3, 2, 0, 0));
}
private final int[][] directions = new int[][]{{-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {-2, 1}, {-2, -1}, {2, 1}, {2, -1}};
public double knightProbability(int n, int k, int row, int column) {
// 定义 f[i][j][p] 表示从位置 (i,j) 出发,步数不超过 p 步,最后仍在棋盘内的概率
double[][][] f = new double[n][n][k + 1];
// 初始化走 0 步的概率
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
f[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[] direction : directions) {
int nx = i + direction[0];
int ny = j + direction[1];
// 判断是否在棋盘内
if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
continue;
}
// 在上一步的概率上除以 8 就是这一步概率
f[i][j][p] += f[nx][ny][p - 1] / 8;
}
}
}
}
return f[row][column][k];
}
}