【Day 59 】2023-08-07 - 688. “马”在棋盘上的概率

[azl397985856]

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

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/knight-probability-in-chessboard/

前置知识

• 动态规划
• 数组

  题目描述

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

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

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

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

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

[freesan44]

class Solution {
    private let dir = [[-1, -2], [1, -2], [2, -1], [2, 1], [1, 2], [-1, 2], [-2, 1], [-2, -1]]

    func knightProbability(_ N: Int, _ K: Int, _ r: Int, _ c: Int) -> Double {
        var dp = Array(repeating: Array(repeating: 0.0, count: N), count: N)
        dp[r][c] = 1

        for step in 1...K {

            var dpTemp = Array(repeating: Array(repeating: 0.0, count: N), count: N)

            for i in 0..<N {
                for j in 0..<N {
                    for direction in dir {

                        let lastR = i - direction[0]
                        let lastC = j - direction[1]
                        if lastR >= 0 && lastR < N && lastC >= 0 && lastC < N {
                            dpTemp[i][j] += dp[lastR][lastC] * 0.125
                        }
                    }
                }
            }

            dp = dpTemp
        }

        var res = 0.0

        for i in 0..<N {
            for j in 0..<N {
                res += dp[i][j]
            }
        }

        return res
    }
}

[GuitarYs]

class Solution:
    def knightProbability(self, N: int, K: int, r: int, c: int) -> float:
        directions = [(-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)]
        dp = [[0] * N for _ in range(N)]
        dp[r][c] = 1

        for _ in range(K):
            temp = [[0] * N for _ in range(N)]
            for i in range(N):
                for j in range(N):
                    for d in directions:
                        nr, nc = i + d[0], j + d[1]
                        if 0 <= nr < N and 0 <= nc < N:
                            temp[nr][nc] += dp[i][j] / 8.0
            dp = temp
        prob = 0
        for i in range(N):
            for j in range(N):
                prob += dp[i][j]
        return prob

[Diana21170648]

思路

动态规划先确定八个方向，再分贝求概率，再得出结果

代码

class Solution:
    def knightProbability(self, n: int, k: int, row: int, col: int) -> float:
        directions=[[-1,-2],[1,-2],[2,-1],[2,1],[1,2],[-1,2],[-2,1],[-2,-1]]
        dp=[[0.0]*n for _ in range(n)]
        dp[row][col]=1.0
        for step in range(1,k+1):
            dp_temp=[[0.0]*n for _ in range(n)]
            for i in range(n):
                for j in range(n):
                    for direction in directions:
                        old_row=i-direction[0]
                        old_col=j-direction[1]
                        if 0<=old_row<n and 0<=old_col<n:
                            dp_temp[i][j]+=dp[old_row][old_col]*0.125
            dp=dp_temp
        res=0.0
        for i in range(n):
            for j in range(n):
                res+=dp[i][j]
        return res

复杂度分析

• 时间复杂度：O(k*N^2)，其中 N 为数组长度。
• 空间复杂度：O(N^2)

[Momogir]

空间复杂度 O（n*n*k）
时间复杂度 O（n*n*k）
定义dp[step][i][j] 表示骑士从棋盘上的点（i，j）出发，走了step步时仍然留在棋盘的概率。
当点(i,j)不在棋盘上时候，dp[step][i][j]=0
当点(i,j)在棋盘上且step=0的时候，dp[step][i][j]=1
其他，dp[step][i][j]=1/8 * all dp[step-1][i+di][j+dj],即每个分支的概率之和
‘’‘
class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        dp=[[[0]*n for _ in range(n)] for _ in range(k+1)]
        for step in range(k+1):
            for i in range(n):
                for j in range(n):
                    if step == 0:
                         dp[step][i][j] = 1
                    else:
                        for di, dj in ((-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)):
                            ni,nj=i+di,j+dj
                            if 0<=ni<n and 0<=nj<n:
                                dp[step][i][j]+=dp[step-1][ni][nj]/8
        return dp[k][row][column]

[huizsh]

class Solution {

    private int[][] dir = {{-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}};

    public double knightProbability(int N, int K, int r, int c) {

        double[][] dp = new double[N][N];
        dp[r][c] = 1;

        for (int step = 1; step <= K; step++) {

            double[][] dpTemp = new double[N][N];

            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    for (int[] direction : dir) {

                        int lastR = i - direction[0];
                        int lastC = j - direction[1];
                        if (lastR >= 0 && lastR < N && lastC >= 0 && lastC < N)
                            dpTemp[i][j] += dp[lastR][lastC] * 0.125;
                    }

            dp = dpTemp;
        }

        double res = 0;

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                res += dp[i][j];

        return res;
    }
}

[snmyj]

class Solution {
    static int[][] dirs = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}};

    public double knightProbability(int n, int k, int row, int column) {
        double[][][] dp = new double[k + 1][n][n];
        for (int step = 0; step <= k; step++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (step == 0) {
                        dp[step][i][j] = 1;
                    } else {
                        for (int[] dir : dirs) {
                            int ni = i + dir[0], nj = j + dir[1];
                            if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                                dp[step][i][j] += dp[step - 1][ni][nj] / 8;
                            }
                        }
                    }
                }
            }
        }
        return dp[k][row][column];
    }
}

[Beanza]

class Solution { static int[][] dirs = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}};

public double knightProbability(int n, int k, int row, int column) {
    double[][][] dp = new double[k + 1][n][n];
    for (int step = 0; step <= k; step++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (step == 0) {
                    dp[step][i][j] = 1;
                } else {
                    for (int[] dir : dirs) {
                        int ni = i + dir[0], nj = j + dir[1];
                        if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                            dp[step][i][j] += dp[step - 1][ni][nj] / 8;
                        }
                    }
                }
            }
        }
    }
    return dp[k][row][column];
}

}

[Fuku-L]

代码

class Solution {
    static int[][] dirs = {{-2,-1}, {-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};

    public double knightProbability(int n, int k, int row, int column) {
        double[][][] dp = new double[k+1][n][n];
        for(int step = 0; step <= k; step++){
            for(int i = 0; i<n; i++){
                for(int j = 0; j<n; j++){
                    if(step == 0){
                        dp[step][i][j] = 1;
                    } else {
                        for(int[] dir:dirs){
                            int ni = i+dir[0], nj = j + dir[1];
                            if(ni >= 0 && ni < n && nj >=0 && nj < n) {
                                dp[step][i][j] += dp[step - 1][ni][nj] / 8;
                            }
                        }
                    }
                }
            }
        }

        return dp[k][row][column];
    }
}

[Alexno1no2]

# 思路
# 1、定义状态：“马” 仍留在棋盘上的概率 dp[i][j]： 位置(i, j)有马的概率
# 2、初始化状态：dp[r][c] = 1
# 3、状态转移使用两个dp仓库，cur记录当前概率，nxt记录移动一次以后的概率 nxt[x][y] += cur[i][j] / 8 其中，(x, y) 是移动后位置， (i, j) 是移动前位置表示 (i, j) 有 1/8 的概率移动到 (x, y)
# 4、返回当前所有位置的概率和

class Solution:
    def knightProbability(self, N: int, K: int, r: int, c: int) -> float:
        cur = [[0] * N for _ in range(N)]
        cur[r][c] = 1
        for _ in range(K):
            nxt = [[0] * N for _ in range(N)]
            for i in range(N):
                for j in range(N):
                    for x, y in ((i + 2, j + 1), (i + 2, j - 1), (i - 2, j + 1), (i - 2, j - 1), 
                                (i + 1, j + 2), (i - 1, j + 2), (i + 1, j - 2), (i - 1, j - 2)):
                        if 0 <= x < N and 0 <= y < N:
                            nxt[x][y] += cur[i][j] / 8
            cur = nxt
        return sum(map(sum, cur))

[passengersa]

class Solution { int[][] dirs = new int[][]{{-1,-2},{-1,2},{1,-2},{1,2},{-2,1},{-2,-1},{2,1},{2,-1}}; public double knightProbability(int n, int k, int row, int column) { 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; } } for (int p = 1; p <= k; p++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int[] d : dirs) { int nx = i + d[0], ny = j + d[1]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; f[i][j][p] += f[nx][ny][p - 1] / 8; } } } } return f[row][column][k]; } }