Description

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

knight

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

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];
    }
};

LeetCode-688 Knight Probability in Chessboard