> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/zou-ge/knight-probability-in-chessboard.md).

# Knight Probability in Chessboard

<https://leetcode.com/problems/knight-probability-in-chessboard/description/>

> On an NxN chessboard, a knight starts at the r-th row and c-th column and attempts to make exactly K moves. The rows and columns are 0 indexed, so the top-left square is (0, 0), and the bottom-right square is (N-1, N-1).
>
> A chess knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square 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:
>
> Input: 3, 2, 0, 0
>
> Output: 0.0625
>
> 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.

## Thoughts

给定Ｎ＊Ｎ矩阵，设F(i, j, k)为走k步还在格子上的概率.

先来看看例子是怎么算的，1/8 \* 2/8 + 1/8\*2/8 = 0.0625，其中1/8为从当前位置（0,0）移动一步（第二步）能到达的位置（1，2）的概率，2/8是从(1,2)移动一步（第一步，也就是最后一步）还在棋盘的概率，也就是说从我们当前位置移动K步还在棋盘的概率为sum\_xy(P\_x,y(K-1)). 当K为0，则f(i,j)肯定在棋盘上所以概率为1.

## Code

```
class Solution {
    public double knightProbability(int N, int K, int r, int c) {
        double[][][] f = new double[N][N][K + 1];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                f[i][j][0] = 1.0;
            }
        }

         for (int k = 1; k <= K; k++) {                                    
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (i - 1 >= 0) {
                        if (j - 2 >= 0) {
                            f[i][j][k] += 0.125 * f[i - 1][j - 2][k - 1];
                        }
                        if (j + 2 < N) {
                            f[i][j][k] += 0.125 * f[i - 1][j + 2][k - 1];
                        }
                        if (i - 2 >= 0) {
                            if (j - 1 >= 0) {
                                f[i][j][k] += 0.125 * f[i - 2][j - 1][k - 1];
                            }
                            if (j + 1 < N) {
                                f[i][j][k] += 0.125 * f[i - 2][j + 1][k - 1];
                            }
                        }                                                  
                    }
                    if (i + 1 < N) {
                        if (j - 2 >= 0) {
                            f[i][j][k] += 0.125 * f[i + 1][j - 2][k - 1];
                        }
                        if (j + 2 < N) {
                            f[i][j][k] += 0.125 * f[i + 1][j + 2][k - 1];
                        }
                        if (i + 2 < N) {
                            if (j - 1 >= 0) {
                                f[i][j][k] += 0.125 * f[i + 2][j - 1][k - 1];
                            }
                            if (j + 1 < N) {
                                f[i][j][k] += 0.125 * f[i + 2][j + 1][k - 1];
                            }
                        }
                    }
                }
            }
         }

        return f[r][c][K];
    }
}
```

## Analysis

时间复杂度为O(mnk)

## Ver.2

把能走的相对位移提前存下来，能减少代码量。

```
class Solution {
    public double knightProbability(int N, int K, int r, int c) {
        double[][][] f = new double[N][N][K + 1];
        int[][] ts = new int[][]{{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                f[i][j][0] = 1.0;
            }
        }

         for (int k = 1; k <= K; k++) {                                    
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    for (int[]t : ts) {
                        int x = i + t[0];
                        int y = j + t[1];
                        if (x < 0 || x >= N || y < 0 || y >= N) {
                            continue;
                        }
                        f[i][j][k] += 0.125 * f[x][y][k - 1];
                    }
                }
            }
         }

        return f[r][c][K];
    }
}
```

节约空间版, 别忘了重置.

```
class Solution {
    public double knightProbability(int N, int K, int r, int c) {
        int[][] dirs = new int[][]{{-2, -1}, {-1, -2}, {1, -2}, {2, -1}, {2, 1}, {-1, 2}, {-2, 1}, {1, 2}};
        double[][][] f = new double[N][N][2];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                f[i][j][0] = 1;
            }
        }

        for (int k = 1; k <= K; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    f[i][j][k % 2] = 0;
                    for (int[] dir : dirs) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (x >= 0 && x < N && y >= 0 && y < N) {
                            f[i][j][k % 2] += 0.125 * f[x][y][(k - 1) % 2];
                        }
                    }
                }
            }
        }

        return f[r][c][K % 2];
    }
}
```