网站的建设需要多少,深圳龙华汽车网站建设,自己可以开发app软件,商城小程序公司文章目录1. 题目2. 解题1. 题目
已知一个 NxN 的国际象棋棋盘#xff0c;棋盘的行号和列号都是从 0 开始。即最左上角的格子记为 (0, 0)#xff0c;最右下角的记为 (N-1, N-1)。
现有一个 “马”#xff08;也译作 “骑士”#xff09;位于 (r, c) #xff0c;并打算进行…
文章目录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 552. 学生出勤记录 II动态规划 LeetCode 576. 出界的路径数动态规划 LeetCode 935. 骑士拨号器动态规划
dp[i][j][k] 表示在 (i, j) 时还剩 k 次跳动机会时的概率
class Solution {
public:double knightProbability(int N, int K, int r, int c) {vectorvectorvectordouble dp(N, vectorvectordouble(N, vectordouble(K1, 0.0)));dp[r][c][K] 1.0;vectorvectorint 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(x0 xN y0 yN){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阿明一起加油、一起学习进步
