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