在一个 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

    1. class Solution {
    2.     //f[i][j][p] : 从i,j出发,经过p步仍在棋盘内得概率
    3.     int[][] dirs = new int[][]{{-1,-2},{-1,2},{1,-2},{1,2},{-2,1},{-2,-1},{2,1},{2,-1}};
    4.     public double knightProbability(int n, int k, int row, int column) {
    5.         double[][][] f = new double[n][n][k+1];
    6.         for (int i = 0; i < n; ++i) 
    7.             for (int j = 0; j < n; ++j) f[i][j][0] = 1;
    8.         for (int p = 1; p <= k; ++p) 
    9.             for (int i = 0; i < n; ++i)
    10.                 for (int j = 0; j < n; ++j) 
    11.                     for (int[] dir : dirs) {
    12.                         int nx = i + dir[0], ny = j + dir[1];
    13.                         if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
    14.                         f[i][j][p] += f[nx][ny][p-1]/8;
    15.                     }
    16.         return f[row][column][k];
    17.     }
    18. }