Description

给定$n\times n$大小的棋盘，以及马的起始坐标$(row,column)$（坐标是从0算起），求$k$次移动后马仍在棋盘上的概率

补充国际象棋中马的移动方式，见上图

Constraints

• $1\le n\le 25$
• $0\le k\le 100$
• $0\le row,column\le n-1$

Solution

可以定义一个$step$来消除后效性

设$dp[step][i][j]$: 从$(i,j)$出发，走了$step$步仍在chessboard的概率

Code

class Solution {
public:
    double knightProbability(int n, int k, int row, int column) {
        double dp[101][26][26] {};
        for(auto &vec : dp[0]) for(auto &v : vec) v = 1;
        const int dx[] = {1, 2, 2, 1, -1, -2, -2, -1};
        const int dy[] = {2, 1, -1, -2, -2, -1, 1, 2};
        for(int step = 1; step <= k; ++step) {
            for(int x = 0; x < n; ++x) {
                for(int y = 0; y < n; ++y) {
                    for(int d = 0; d < 8; ++d) {
                        int nx = x + dx[d];
                        int ny = y + dy[d];
                        if(nx < 0 || nx >= n) continue;
                        if(ny < 0 || ny >= n) continue;
                        dp[step][x][y] += 1.0/8 * dp[step-1][nx][ny];
                    }
                }
            }
        }
        return dp[k][row][column];
    }
};

Link

LeetCode-688 Knight Probability in Chessboard