题意

大意的意思就是在一个棋盘上，马按照象棋中马走日的规则，可以选择走K此后，最后还是留在棋盘的概率。

分析

  • 首先一匹马在任意位置可以选择八个方向走动，称之为方向向量，分别为

    1
    2
    int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};    //方向导向数组
    int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};

  • 其次由于棋盘是有限的，所以如果选择的步伐超出了棋盘，则视为无效。

  • 现在给个例子，模拟一下其的走动方位，N=4，k=3，r=0，c=0

    • 1、一开始的时候，这匹马所在的位置

    • 2、走第一步的时候后可以选择的落脚点：只有两个方向是可以选择的呢，其余的都是超出了棋盘的范围

      走完第一步后的矩阵如下：

    • 3、仿照上述过程，第二步的走向如下

​     走完第二步后的矩阵如下：

![](https://cdn.jsdelivr.net/gh/xiewende/blog_img/20210524%E9%A9%AC%E5%9C%A8%E6%A3%8B%E7%9B%98%E7%9A%84%E6%A6%82%E7%8E%87/5.jpg)

​

  • 第三步可选的落脚点如下：

    走完第三步后的矩阵：

  • 到这里，就已经完成了这匹马在棋盘上面的全部可能走法了，最后一个还有 2+2+6+6+2+2 = 20次还留着棋盘上，所以概率就为 20 / 8 8 8

  • 状态转移方程：

    1
    dp[r][c][steps]:表示马在位置（r，c）移动了 steps 次后还留在棋盘上的概率

    根据马的移动，得到如下递归方程 如下

dr，dc就是上面说的方向向量的数组，根据这个递归处理的方程，我们可以采取一个二维数组进行编写，即一新一旧，一步一步更新这些数组，最后求和即可

代码
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
//力扣上的主函数
public double knightProbability(int N, int K, int r, int c) {
       double[][] dp_old = new double[N][N]; //dp_old数组，dp[x][y]表示第i次到达dp[x][y]的方案数
       double[][] dp_new = new double[N][N]; //dp_new数组，dp[i][j]表示第i+1次到达dp[x][y]的方案数
       //初始化
       dp_old[r][c] = 1;   //一开始的位置
       for(int i = 0; i < K; i++){ //K次
           for (int x = 0; x < N; x++) {
               for (int y = 0; y < N; y++) {
                   //四面八方累加dp
                   dp_new[x][y] = computeSumFromDirection(dp_old, x, y);
               }
           }
           //更新两个数组
           dp_old = dp_new;
           dp_new = new double[N][N];
       }
       //遍历这个数组的总和就是落在棋盘内所有格子的方案数
       double in = 0;
       for (int x = 0; x < N; x++) {
           for (int y = 0; y < N; y++) {
               in += dp_old[x][y];
           }
       }
       return in;
   }
//每次的八个方向的走法，并且判断是否越界
   public double computeSumFromDirection(double[][] dp_old, int x, int y){
       double sum = 0;
       int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};    //方向导向数组
       int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};
       for (int i = 0; i < dx.length; i++){
           if(!check(dp_old, x + dx[i], y + dy[i])) continue;
           sum += dp_old[x + dx[i]][y + dy[i]];
       }
       return sum / 8.0;
   }
//给定位置判断是否越界
   public boolean check(double[][] dp_old, int x, int y){     //越界判断
       return x >= 0 && x < dp_old.length && y >= 0 && y < dp_old[0].length;
   }

学习使我快乐！！！