提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

菜鸟的每日力扣系列——688. 骑士在棋盘上的概率(#Day39)

2023-02-18 16:23:56 时间

力扣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

相关文章