盛日辉的博客
0%

Leetcode-688-骑士在棋盘上的概率

发表于 分类于

题目

688. 骑士在棋盘上的概率
难度：中等

在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，并尝试进行 k 次移动。行和列是 从 0 开始 的，所以左上单元格是 (0,0) ，右下单元格是 (n - 1, n - 1) 。

象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。

每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。

骑士继续移动，直到它走了 k 步或离开了棋盘。

返回 骑士在棋盘停止移动后仍留在棋盘上的概率 。

 

示例 1：

输入: n = 3, k = 2, row = 0, column = 0
输出: 0.0625
解释: 有两步(到(1,2)，(2,1))可以让骑士留在棋盘上。
在每一个位置上，也有两种移动可以让骑士留在棋盘上。
骑士留在棋盘上的总概率是0.0625。

示例 2：

输入: n = 1, k = 0, row = 0, column = 0
输出: 1.00000

 

提示:

  • 1 <= n <= 25
  • 0 <= k <= 100
  • 0 <= row, column <= n

思路一：广度优先搜索（BFS）

题目不是很难理解，容易想到BFS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
	    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        Dirs = [(-1, -2), (1, -2),
                (-2, -1), (2, -1),
                (-2, 1), (2, 1),
                (-1, 2), (1, 2)]
        q = deque()
        q.append((row, column, k))
        cnt = 0
        while q:
            r, c, kk = q.popleft()
            # # 取出kk==0，cnt+1
            # # 也就是，走到最后一步再计数
            if kk == 0:
                cnt += 1
                continue
            for x, y in Dirs:
                if 0 <= r + x < n and 0 <= c + y < n:
                    q.append((r + x, c + y, kk - 1))
        return cnt / pow(8, k)

但这也很容易地超出了时间限制。

思路二：动态规划

看了一下官解，没想到用的是动态规划。尝试自己写了一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        Dirs = [(-1, -2), (1, -2),
                (-2, -1), (2, -1),
                (-2, 1), (2, 1),
                (-1, 2), (1, 2)]
        dp=[[[0]* n for _ in range(n)]for _ in range(k+1)]
        dp[0][row][column]=1
        for step in range(k):
            for i in range(n):
                for j in range(n):
                    if dp[step][i][j]>0:
                        for di,dj in Dirs:
                            ni,nj=i+di,j+dj
                            if 0<=ni<n and 0<=nj<n:
                                dp[step+1][ni][nj]+=1
        cnt=0
        for i in range(n):
            cnt+=sum(dp[-1][i])
        print(dp[-1])
        return cnt/pow(8,k)

但是这样出现了错误，原因是在最后一步（step=k-1）的dp[step+1][ni][nj]+=1，加的只是这一步的情况，没有算上之前其实还有很多能到i,j的情况。

将dp[step+1][ni][nj]+=1修改为dp[step + 1][ni][nj] += dp[step][i][j],成功通过！而且比官解的好！

官解：
它的状态值dp[step][i][j]指的是从(i,j)出发第step步后还在棋盘上的概率，状态转移方程是： $ dp[step][i][j] += \frac{1}{8} + \sum_{di,dj} dp[step-1][i+di][j+dj] , (di,dj)\in \{(-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)\}, 0\leq i,j,i+di,j+dj <n $ 。
也不难理解，因为(i,j)下一步有8种可能的走法，那(i+di,j+dj)的概率就是 $\frac{1}{8}$ (i,j)的概率。换个角度讲也就是，有8种可能走到它(i,j)这，那走到(i,j)的概率就是$\sum_{di,dj} dp[step-1][i+di][j+dj]$。
那为什么最后只要输出dp[k][row][column]就好了呢？
我觉得可以倒过来走，以n=3,k=1,row=0,colmn=0为例，(0,0)在第1步往回走，有0.25的概率留在棋盘上，这就是答案。将初始值全部设为1，遍历所有点进行状态转移方程的计算，所得的结果dp[k][i][j]就是(i,j)走了k步之后仍然留在棋盘上的概率。将k扩展来解释状态转移方程，第k步(i,j)仍然留在棋盘的概率是由第k-1步对应8个点的状态值计算而来，每个点的状态值就是该店走那么多步仍然留在棋盘的概率。
当然了，超出棋盘范围的值都是0啦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        dp = [[[0] * n for _ in range(n)] for _ in range(k + 1)]
        for step in range(k + 1):
            for i in range(n):
                for j in range(n):
                    if step == 0:
                        dp[step][i][j] = 1
                    else:
                        for di, dj in ((-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)):
                            ni, nj = i + di, j + dj
                            if 0 <= ni < n and 0 <= nj < n:
                                dp[step][i][j] += dp[step - 1][ni][nj] / 8
        return dp[k][row][column]

# 作者：LeetCode-Solution
# 链接：https://leetcode-cn.com/problems/knight-probability-in-chessboard/solution/qi-shi-zai-qi-pan-shang-de-gai-lu-by-lee-2qhk/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我对官解的优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        Dirs = ((-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2))
        dp = [[[0] * (n + 4) for _ in range(n + 4)] for _ in range(2)]
        for i in range(2, 2 + n):
            for j in range(2, 2 + n):
                dp[0][i][j] = 1
        for step in range(1, k + 1):
            for i in range(2, 2 + n):
                for j in range(2, 2 + n):
                    dp[step % 2][i][j] = 0
                    for di, dj in Dirs:
                        ni, nj = i + di, j + dj
                        dp[step % 2][i][j] += dp[1 - step % 2][ni][nj] / 8
        return dp[k % 2][row + 2][column + 2]

提交记录

提交记录.png