688. “马”在棋盘上的概率#

1
已知一个 NxN 的国际象棋棋盘，棋盘的行号和列号都是从 0 开始。
2

3
即最左上角的格子记为 (0, 0)，最右下角的记为 (N-1, N-1)。
4

5
现有一个 “马”（也译作 “骑士”）位于 (r, c) ，并打算进行 K 次移动。
6

7
如下图所示，国际象棋的 “马” 每一步先沿水平或垂直方向移动 2 个格子，
8

9
然后向与之相垂直的方向再移动 1 个格子，共有 8 个可选的位置。
10

11
现在 “马” 每一步都从可选的位置（包括棋盘外部的）中独立随机地选择一个进行移动，
12

13
直到移动了 K 次或跳到了棋盘外面。
14

15
求移动结束后，“马” 仍留在棋盘上的概率。
16

17
示例：
18

19
输入: 3, 2, 0, 0
20
输出: 0.0625
21
解释:
22
输入的数据依次为 N, K, r, c
23
第 1 步时，有且只有 2 种走法令 “马” 可以留在棋盘上（跳到（1,2）或（2,1））。
24

25
对于以上的两种情况，各自在第2步均有且只有2种走法令 “马” 仍然留在棋盘上。
26

27
所以 “马” 在结束后仍在棋盘上的概率为 0.0625。
28

29

30
注意：
31

32
N 的取值范围为 [1, 25]
33
K 的取值范围为 [0, 100]
34
开始时，“马” 总是位于棋盘上

1
class Solution {
2
public:
3
    int d[8][2] = {
4
                    {1, 2}, {2, 1}, {2, - 1}, {1, -2},
5
                    {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}
6
         };
7
    double knightProbability(int N, int K, int r, int c) {
8
        if (K == 0) return 1.0;
9
        vector<vector<double> > dp(N, vector<double>(N, 1));
10
        for (int k = 1; k <= K; ++k) {
11
            auto ans = dp;
12
            for (int i = 0; i < N; ++i) {
13
                for (int j = 0; j < N; ++j) {
14
                    ans[i][j] = 0;
15
                    for (int l = 0; l < 8; ++l) {
16
                        int r = i + d[l][0];
17
                        int c = j + d[l][1];
18
                        if (r >= 0 && r < N && c >= 0 && c < N) {
19
                            ans[i][j] += dp[r][c] / 8;
20
                        }
21
                    }
22
                }
23
            }
24
            swap(ans, dp);
25
        }
26
        return dp[r][c];
27
    }
28
};