Leetcode 688.马在棋盘上的概率

Posted on |

688. “马”在棋盘上的概率

题目

已知一个 NxN 的国际象棋棋盘，棋盘的行号和列号都是从 0 开始。即最左上角的格子记为 (0, 0)，最右下角的记为 (N-1, N-1)。

现有一个 “马”（也译作 “骑士”）位于 (r, c) ，并打算进行 K 次移动。

如下图所示，国际象棋的 “马” 每一步先沿水平或垂直方向移动 2 个格子，然后向与之相垂直的方向再移动 1 个格子，共有 8 个可选的位置。

现在 “马” 每一步都从可选的位置（包括棋盘外部的）中独立随机地选择一个进行移动，直到移动了 K 次或跳到了棋盘外面。

求移动结束后，“马” 仍留在棋盘上的概率。

1
2
3
4
5
6
7
8
示例：

输入: 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]
开始时，“马” 总是位于棋盘上

方法

方法1：动态规划

令f[r][c][step]表示，经过step后落在棋盘(r,c)上的概率，得出公式

dr,dc表示下一步要走的偏量，就是求只要在step-1步骤中所有可能的位置到达step步骤中的(r,c)的概率综合。最后只要求出最后一步棋盘上所有位置上概率综合。

很显然，在每一个steps步骤中，只需要当前步骤steps的数据，和前一个steps-1的数据，就可以完成计算，所以f[r][c][steps] 这个3维数组，完全可以用两个2维数组代替。
所以用，dp2表示 f[][][steps]，用dp表示f[][][steps-1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def knightProbability(self, N, K, r, c):
        """
        :type N: int
        :type K: int
        :type r: int
        :type c: int
        :rtype: float
        """
        dp=[[0]*N for _ in range(N)]          # 初始化dp，记录第step-1步时，概率分布f[][][step-1]
        dp[r][c]=1
        for _ in range(K):
            dp2=[[0]*N for _ in range(N)]     # 初始化dp2，记录当前步骤step的概率分布
            for r in range(N):
                for c in range(N):
                    for dr,dc in zip((2,2,-2,-2,1,1,-1,-1),(1,-1,1,-1,2,-2,2,-2)):                      # 判断是否出界
                        if 0<=r+dr<=N-1 and 0<=c+dc<=N-1:
                            dp2[r+dr][c+dc]+=dp[r][c]/8.0   # 只保留棋盘内的概率
            dp=dp2                            # 更新step-1步骤中的期盼概率分布
        return sum(map(sum,dp))               # 把落在棋盘上的所有位置的概率加起来，就是最后落在棋盘上的概率