原文链接: https://leetcode-cn.com/problems/knight-probability-in-chessboard

英文原文

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

中文题目

已知一个 NxN 的国际象棋棋盘，棋盘的行号和列号都是从 0 开始。即最左上角的格子记为 (0, 0)，最右下角的记为 (N-1, N-1)。 

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

如下图所示，国际象棋的 “马” 每一步先沿水平或垂直方向移动 2 个格子，然后向与之相垂直的方向再移动 1 个格子，共有 8 个可选的位置。

 

 

现在 “马” 每一步都从可选的位置（包括棋盘外部的）中独立随机地选择一个进行移动，直到移动了 K 次或跳到了棋盘外面。

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

 

示例：

输入: 3, 2, 0, 0
输出: 0.0625
解释: 
输入的数据依次为 N, K, r, c
第 1 步时，有且只有 2 种走法令 “马” 可以留在棋盘上（跳到（1,2）或（2,1））。对于以上的两种情况，各自在第2步均有且只有2种走法令 “马” 仍然留在棋盘上。
所以 “马” 在结束后仍在棋盘上的概率为 0.0625。

 

注意：

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

通过代码

官方题解

方法一：动态规划

算法：

• 令 f[r][c][steps] 代表马在位置 (r, c) 移动了 steps 次以后还留在棋盘上的概率，根据马的移动方式，我们有以下递归：
  $$f[r][c][steps] = \sum_{dr, dc} f[r+dr][c+dc][steps-1] / 8.0$$
• 根据题目我们可以知道 $(dr, dc)$ 的可能数据对是 $(2, 1),$ $(2, -1),$ $(-2, 1),$ $(-2, -1),$ $(1, 2),$ $(1, -2),$ $(-1, 2),$ $(-1, -2)$。
• 我们将使用二维的 dp 和 dp2 来存储我们的数据，而不是使用三维数组 f。dp2 代表 f[][][steps]，dp 代表 f[][][steps-1]。

[solution1-Java]
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;
    }
}

[solution1-Python]
class Solution(object):
    def knightProbability(self, N, K, r, c):
        dp = [[0] * N for _ in xrange(N)]
        dp[r][c] = 1
        for _ in xrange(K):
            dp2 = [[0] * N for _ in xrange(N)]
            for r, row in enumerate(dp):
                for c, val in enumerate(row):
                    for dr, dc in ((2,1),(2,-1),(-2,1),(-2,-1),
                                   (1,2),(1,-2),(-1,2),(-1,-2)):
                        if 0 <= r + dr < N and 0 <= c + dc < N:
                            dp2[r+dr][c+dc] += val / 8.0
            dp = dp2

        return sum(map(sum, dp))

复杂度分析

• 时间复杂度：$O(N^2 K)$。其中 $N, K$ 为题目中的定义。我们对 $N^2$ 元素的每一层 dp 进行 $O(1)$ 工作，并且考虑了 $K$ 层。
• 空间复杂度：$O(N^2)$，dp 和 dp2 的大小。

方法二：矩阵求幂

方法 1 中表示的状态重复表达了过渡到其他的线性组合的状态。 任何情况下，我们都可以将整个转换表示为这些线性组合的矩阵。然后，这个矩阵的第 $n$ 次方代表了 $n$ 移动的转换，因此我们可以将问题简化为矩阵求幂问题。

算法：

• 首先，我们可以利用棋盘上的对称性。马可能有 $n^2$ 的状态（假设它在板上）。由于横轴、纵轴和对角线的对称性，我们可以假设骑士在棋盘的左上象限，并且列数等于或大于行数。对于任何一个位置，通过满足条件通过轴反射得到位置将是该位置的标准索引。
• 这将使状态数从 $N^2$ 减少到大约 $\frac{N^2}{8}$，这使得在这个 $O(\frac{N^2}{8}) \times O(\frac{N^2}{8})$ 矩阵上下求幂大约快 $8^3$ 倍。
• 现在，如果我们知道每一个状态在一次移动后都会变成某种状态的线性组合，那么让我们写一个过渡矩阵 $\mathcal{T}$，其中 $\mathcal{T}$ 的第 $i$ 行代表了第 $i$ 个状态的线性组合。然后，$\mathcal{T}^n$ 表示 $n$ 次移动的转换，我们需要第 $i$ 行的总和，其中 $i$ 是起始位置的索引。

[solution2-Java]
class Solution {
    public double knightProbability(int N, int K, int sr, int sc) {
        int[] dr = new int[]{-1, -1, 1, 1, -2, -2, 2, 2};
        int[] dc = new int[]{2, -2, 2, -2, 1, -1, 1, -1};

        int[] index = new int[N * N];
        int t = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (r * N + c == canonical(r, c, N)) {
                    index[r * N + c] = t;
                    t++;
                } else {
                    index[r * N + c] = index[canonical(r, c, N)];
                }
            }
        }

        double[][] T = new double[t][t];
        int curRow = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (r * N + c == canonical(r, c, N)) {
                    for (int k = 0; k < 8; k++) {
                        int cr = r + dr[k], cc = c + dc[k];
                        if (0 <= cr && cr < N && 0 <= cc && cc < N) {
                            T[curRow][index[canonical(cr, cc, N)]] += 0.125;
                        }
                    }
                    curRow++;
                }
            }
        }

        double[] row = matrixExpo(T, K)[index[sr*N + sc]];
        double ans = 0.0;
        for (double x: row) ans += x;
        return ans;
    }

    public int canonical(int r, int c, int N) {
        if (2*r > N) r = N-1-r;
        if (2*c > N) c = N-1-c;
        if (r > c) {
            int t = r;
            r = c;
            c = t;
        }
        return r * N + c;
    }
    public double[][] matrixMult(double[][] A, double[][] B) {
        double[][] ans = new double[A.length][A.length];
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B[0].length; j++) {
                for (int k = 0; k < B.length; k++) {
                    ans[i][j] += A[i][k] * B[k][j];
                }
            }
        }
        return ans;
    }
    public double[][] matrixExpo(double[][] A, int pow) {
        double[][] ans = new double[A.length][A.length];
        for (int i = 0; i < A.length; i++) ans[i][i] = 1;
        if (pow == 0) return ans;
        if (pow == 1) return A;
        if (pow % 2 == 1) return matrixMult(matrixExpo(A, pow-1), A);
        double[][] B = matrixExpo(A, pow / 2);
        return matrixMult(B, B);
    }
}

[solution2-Python]
class Solution(object):
    def knightProbability(self, N, K, sr, sc):
        def canonical(r, c):
            if 2 * r > N: r = N - 1 - r
            if 2 * c > N: c = N - 1 - c
            if r > c: r, c = c, r
            return r*N + c

        def matrix_mult(A, B):
            ZB = zip(*B)
            return [[sum(a * b for a, b in zip(row, col))
                     for col in ZB] for row in A]

        def matrix_expo(A, K):
            if K == 0:
                return [[+(i==j) for j in xrange(len(A))]
                        for i in xrange(len(A))]
            if K == 1:
                return A
            elif K % 2:
                return matrix_mult(matrix_expo(A, K-1), A)
            B = matrix_expo(A, K/2)
            return matrix_mult(B, B)

        index = [0] * (N*N)
        t = 0
        for r in xrange(N):
            for c in xrange(N):
                if r*N + c == canonical(r, c):
                    index[r*N + c] = t
                    t += 1
                else:
                    index[r*N + c] = index[canonical(r, c)]

        T = []
        for r in xrange(N):
            for c in xrange(N):
                if r*N + c == canonical(r, c):
                    row = [0] * t
                    for dr, dc in ((2,1),(2,-1),(-2,1),(-2,-1),
                                    (1,2),(1,-2),(-1,2),(-1,-2)):
                        if 0 <= r+dr < N and 0 <= c+dc < N:
                            row[index[(r+dr)*N + c+dc]] += 0.125
                    T.append(row)

        Tk = matrix_expo(T, K)
        i = index[sr * N + sc]
        return sum(Tk[i])

复杂度分析

• 时间复杂度：$O(N^6 \log(K))$。其中 $N, K$ 为题目中的定义。大约有 $\frac{N^2}{8}$ 规范状态，这使得我们的矩阵乘法 $O(N^6)$。为了找到这个矩阵的第 $K$ 次幂，我们做了 $O(\log(K))$ matrix乘法。
• 空间复杂度：$O(N^4)$，矩阵有大约 $\frac{N^4}{64}$ 个元素。

统计信息

通过次数	提交次数	AC比率
8455	16471	51.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
出界的路径数	中等