leetcode 688. “马”在棋盘上的概率
2024-10-20 20:51:51
题目描述:
已知一个 NxN 的国际象棋棋盘,棋盘的行号和列号都是从 0 开始。即最左上角的格子记为 (0, 0),最右下角的记为 (N-1, N-1)。
现有一个 “马”(也译作 “骑士”)位于 (r, c) ,并打算进行 K 次移动。
如下图所示,国际象棋的 “马” 每一步先沿水平或垂直方向移动 2 个格子,然后向与之相垂直的方向再移动 1 个格子,共有 8 个可选的位置。
思路分析:
思路1: 首先想到的是用dfs,但是这样会超时,最坏情况可能达到8的100次方。
思路2: 三维dp,dp[i][j][k]表示在点(i, j)上移动了k次后改点仍然位于棋盘上的概率。首先,初始条件dp[i][j][0]=1。接下来四层的循环,最外层为1到k次的移动,接下来是位置i,j的两重循环,最后是移动方向1到8的循环,dp[i][j][num] = sum(dp[i][j][num-1]*(1.0/8.0)),即当前点k次的概率为所有k-1次的概率之和。
代码:
class Solution {
public:
double knightProbability(int N, int K, int r, int c) {
if(K<=)
return 1.0;
if(N< || r< || r>=N || c< || c>=N)
return 0.0;
double dp[][][];
int direction[][] = {{-, -}, {, -}, {-, }, {, }, {-, -}, {-, }, {, -}, {, }};
for(int i=; i<N; i++)
for(int j=; j<N; j++)
dp[i][j][]=;
for(int num=; num<=K; num++)
{
for(int i=; i<N; i++)
{
for(int j=; j<N; j++)
{
double tmp = ;
for(int l=; l<; l++)
{
int x = i+direction[l][];
int y = j+direction[l][];
if(x< || y< || x>=N || y>=N)
continue;
tmp += (1.0/8.0)*dp[x][y][num-];
}
dp[i][j][num] = tmp;
}
}
}
return dp[r][c][K];
}
};
最新文章
- boost asio tcp server 拆分
- NSOperation
- gerrit error: unpack failed: error Permission denied
- Apache Qpid Python 1.35.0 发布
- EhCache 分布式缓存/缓存集群(转)
- 【JAVA】导出jar包时,Class files on classpath not found
- sed(查找替换) 与awk(提取字段)
- 项目管理实践【六】自动同步数据库【Using Visual Studio with Source Control System to synchronize database automatically】
- 规范 : 过程 : login cookies sessionTimeOut
- 你真的了解volatile吗,关于volatile的那些事
- Effective Java 第三版——28. 列表优于数组
- JavaScript 数值Number类型详解
- Dynamics CRM 通过RetrieveEntityRibbonRequest和RetrieveApplicationRibbonRequest导出实体的Ribbon XML
- python 列表 元祖
- python 类的介绍实例
- PostGIS中生成GUID字段值
- LeetCode(27): 移除元素
- 【Java】链表中存储对象的问题
- 【javascript】javascript中function(){},function(){}(),new function(){},new Function()
- SQL Operations Studio的安装和使用
热门文章
- 组件切换方式(Vue.js)
- Beego 学习笔记14:Session控制
- Java 使用properties配置文件加载配置
- C语言几个术语: 数据对象,左值,右值
- 多态典型用例之virtual
- PAT 乙级 1005.继续(3n+1)猜想 C++/Java
- Explorer(2019年牛客多校第八场E题+线段树+可撤销并查集)
- phpstorm通过FileWatchers配置自动格式化代码插件
- nginx 负载均衡,如何判断某台服务器宕机?
- dotnet core linux 接入支付宝H5支付,提示:System.PlatformNotSupportedException";,";Message";:";&#39;CspParameters&#39; requires Windows Cryptographic API (CAPI), which is not available on this platform.