菜鸟的每日力扣系列——688. 骑士在棋盘上的概率(#Day39)
系列 每日 菜鸟 力扣 概率 棋盘 骑士 688
2023-06-13 09:15:51 时间
力扣688. 骑士在棋盘上的概率
对于在棋盘格/岛屿陆地/矿洞等地图上跳来跳去的问题,都可以优先尝试使用dfs。我们要算骑士留在棋盘上的概率,就需要先找到不满足的边界条件:在做dfs时跳出棋盘即横纵坐标小于0或者大于最大长度时,表明骑士离开了棋盘;假设骑士在棋盘内且k=0时,骑士一定留在棋盘上,概率为1。
然后就是找出骑士可以走的8个方向,假设骑士当前位置在(i, j),那么下一跳可能的位置是[i-1, j-2], [i-2, j-1], [i+1, j-2], [i+2, j-1], [i-2, j+1], [i-1, j+2], [i+1, j+2], [i+2, j+1],每次骑士可以走到这8个方向,每个方向的概率为1/8。而每个方向之后继续进行深搜的概率*1/8的总和则就是骑士留在场上的总概率。
对于本题为了避免运行超时,需要考虑最坏的情况,就是骑士向8个方向都能跳跃且都不离开棋盘这种情况。我们可以增加记忆化,记录骑士跳过的位置,之后再进行跳跃,直到跳不动之前的所有概率之和,作为记忆化搜索的缓存记录。在python中可以使用functools库下的@lru_cache(None)。
from functools import lru_cache
def knightProbability(n: int, k: int, row: int, column: int) -> float:
@lru_cache(None)
def dfs(i, j, k):
if i < 0 or i >= n or j < 0 or j >= n:
return 0
elif k == 0:
return 1
res = 0
for x, y in [[i-1, j-2], [i-2, j-1], [i+1, j-2], [i+2, j-1], [i-2, j+1], [i-1, j+2], [i+1, j+2], [i+2, j+1]]:
res += dfs(x, y, k-1) / 8
return res
return dfs(row, column, k)
n = 3
k = 2
row = 0
column = 0
print(knightProbability(n, k, row, column)) # 0.0625
END
相关文章
- 【每日要闻】我国正在论证载人登月方案;华为Mate50系列将于9月6日发布
- Go系列-构建高性能协程池
- 【Laravel系列7.9】测试
- 菜鸟的每日力扣系列——507. 完美数
- 菜鸟的每日力扣系列——2022. 将一维数组转变成二维数组
- 菜鸟的每日力扣系列——390.消除游戏
- 菜鸟的每日力扣系列——1576. 替换所有的问号
- 菜鸟的每日力扣系列——71. 简化路径
- 菜鸟的每日力扣系列——306. 累加数
- 菜鸟的每日力扣系列——2047. 句子中的有效单词数
- 菜鸟的每日力扣系列——1405. 最长快乐字符串(#Day31)
- 菜鸟的每日力扣系列——1020. 飞地的数量(#Day35)
- 菜鸟的每日力扣系列——1791. 找出星型图的中心节点
- 利用 ALV 实现增删改查系列之二:仅让 ALV 报表某一列允许被编辑试读版
- 【每日要闻】台积电超过三星成全球最大半导体销售公司;iPhone 14系列创首发最快降价纪录
- To B商业史系列 01:在线办公的潮起潮落
- Spark入门实战系列–6.SparkSQL(中)–深入了解SparkSQL运行计划及调优详解大数据
- 小米11系列出现Wi-Fi失效问题 官方回应:支持换新机 赠半年延保
- 小米系列新品曝光:骁龙888 Plus、120W快充都有