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 {
private static 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) {
double[][][] dp = new double[k + 1][n][n];
for (int i = 0; i <= k; i++) {
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
if (i == 0) {
dp[i][x][y] = 1.0;
} else {
for (int[] direction : DIRECTIONS) {
int nextX = x + direction[0], nextY = y + direction[1];
if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n) {
dp[i][x][y] += dp[i - 1][nextX][nextY] / 8;
}
}
}
}
}
}
return dp[k][row][column];
}
}
|