来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/knight-probability-in-chessboard

题目描述

在一个 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

解题思路

一道标准的动态规划题。

需要三重dp(i,j,k) 表示从(i,j) 出发经过k步后还在棋盘上的概率，dp的初始状态为dp(i,j,0)均为1，状态转移方程是

$dp(i,j,l) = \frac{\sum_{m = 0}^{8}dp(i + dx_{m}, j + dy_{m}, l - 1)}{8}$

其中dx = ｛-1 -2 -2 -1 1 2 2 1｝， dy ={-2 -1 1 2 2 1 -1 -2}

最终结果就在dp(row, column, k)中。

代码展示

class Solution {

public:

    double knightProbability(int n, int k, int row, int column) {

        vector<vector<vector<double>>> dp(n, vector<vector<double>>(n, vector<double>(k + 1, 1.0)));

        int dx[8] = {-1, -2, -2, -1, 1, 2,  2,  1};

        int dy[8] = {-2, -1,  1,  2, 2, 1, -1, -2};

        for(int l = 1; l < k + 1; l++)

        {

            for(int i =0; i< n; i++)

            {

                for(int j = 0; j < n; j++)

                {

                    double dSum = 0;

                    for(int m = 0; m < 8; m ++)

                    {

                        int x = i + dx[m];

                        int y = j + dy[m];

                        if(x >= 0 && x < n && y >= 0 && y < n)

                        {

                            dSum += dp[x][y][l - 1];

                        }

                    }

                    dp[i][j][l] = dSum / 8;

                }

            }

        }

        return dp[row][column][k];

    }

};

巴特西

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

题目描述

解题思路

代码展示

运行结果

最新文章

热门文章