文章目錄
- 1. 題目
- 2. 解題
1. 題目
已知一個 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]
開始時，“馬” 總是位于棋盤上
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/knight-probability-in-chessboard
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
2. 解題
類似題目：LeetCode 576. 出界的路徑數（動態規劃）
dp[i][j][k]表示在(i, j)時還剩 k 次跳動機會時的概率
class Solution {
public:
double knightProbability(int N, int K, int r, int c) {
vector<vector<vector<double>>> dp(N, vector<vector<double>>(N, vector<double>(K+1, 0.0)));
dp[r][c][K] = 1.0;
vector<vector<int>> dir = {{2,1},{1,2},{-2,1},{-1,2},{2,-1},{1,-2},{-1,-2},{-2,-1}};
int i, j, k, x, y, d;
for(k = K; k > 0; k--)
{
for(i = 0; i < N; i++)
{
for(j = 0; j < N; j++)
{
for(d = 0; d < 8; d++)
{
x = i + dir[d][0];
y = j + dir[d][1];
if(x>=0 && x<N && y>=0 && y<N)
{
dp[x][y][k-1] += dp[i][j][k]/8.0;
}
}
}
}
}
double ans = 0.0;
for(i = 0; i < N; i++)
for(j = 0; j < N; j++)
ans += dp[i][j][0];
return ans;
}
};
28 ms 8 MB
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/154065.html
標籤：其他
上一篇：【SSM - MyBatis篇11】MyBatis快取，spring整合MyBatis開啟二級快取，MyBatis開啟二級快取