05 August 2008
已知一个 NxN 的国际象棋棋盘，棋盘的行号和列号都是从 0 开始。即最左上角的格子记为 (0, 0)，最右下角的记为 (N-1, N-1)。
现有一个 “马”（也译作 “骑士”）位于 (r, c) ，并打算进行 K 次移动。
如下图所示，国际象棋的 “马” 每一步先沿水平或垂直方向移动 2 个格子，然后向与之相垂直的方向再移动 1 个格子，共有 8 个可选的位置。
现在 “马” 每一步都从可选的位置（包括棋盘外部的）中独立随机地选择一个进行移动，直到移动了 K 次或跳到了棋盘外面。
求移动结束后，“马” 仍留在棋盘上的概率。
On an n x n chessboard, a knight starts at the cell (row, column) and attempts to make exactly k moves. The rows and columns are 0-indexed, so the top-left cell is (0, 0), and the bottom-right cell is (n - 1, n - 1).
A chess knight has eight possible moves it can make, as illustrated below. Each move is two cells in a cardinal direction, then one cell in an orthogonal direction.
Each time the knight is to move, it chooses one of eight possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.
The knight continues moving until it has made exactly k moves or has moved off the chessboard.
Return the probability that the knight remains on the board after it has stopped moving.
Example 1:
Input: n = 3, k = 2, row = 0, column = 0 Output: 0.06250 Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board. From each of those positions, there are also two moves that will keep the knight on the board. The total probability the knight stays on the board is 0.0625. Example 2:
Input: n = 1, k = 0, row = 0, column = 0 Output: 1.00000
Constraints:
1 <= n <= 25 0 <= k <= 100 0 <= row, column <= n
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
class Solution {
public double knightProbability(int N, int K, int sr, int sc) {
double[][] dp = new double[N][N];
int[] dr = new int[]{2, 2, 1, 1, -1, -1, -2, -2};
int[] dc = new int[]{1, -1, 2, -2, 2, -2, 1, -1};
dp[sr][sc] = 1;
for (; K > 0; K--) {
double[][] dp2 = new double[N][N];
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
for (int k = 0; k < 8; k++) {
int cr = r + dr[k];
int cc = c + dc[k];
if (0 <= cr && cr < N && 0 <= cc && cc < N) {
dp2[cr][cc] += dp[r][c] / 8.0;
}
}
}
}
dp = dp2;
}
double ans = 0.0;
for (double[] row: dp) {
for (double x: row) ans += x;
}
return ans;
}
}