Leetcode打卡：骑士在棋盘上的概率

执行结果：通过

题目：骑士在棋盘上的概率

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

代码以及解题思路

代码：

double knightProbability(int n, int k, int r, int c) {
    double dp1[n][n], dp2[n][n];
    memset(dp1, 0, sizeof(dp1));

    int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
    int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
    double (*pre)[n] = dp1, (*cur)[n] = dp2;
    for (int K = 1; K <= k; K++) {
        memset(cur, 0, sizeof(dp1));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int p = 0; p < 8; p++) {
                    int cx = i + dx[p];
                    int cy = j + dy[p];
                    cur[i][j] += ((cx < 0 || cx >= n || cy < 0 || cy >= n) ? 1 : pre[cx][cy]) / 8;
                }
            }
        }
        double (*t)[n] = pre;
        pre = cur, cur = t; 
    }

    return 1 - pre[r][c];

    
}

解题思路：

1. 初始化动态规划数组：
   • 使用两个二维数组 dp1 和 dp2 来存储每一步移动后的概率。dp1 用于存储当前步的概率，dp2 用于存储下一步的概率。
   • 使用 memset 函数将 dp1 初始化为0，因为初始时骑士还未移动，所以所有位置的概率都是0（但这里实际上是为了后续计算方便，初始值对结果无影响，因为我们会从1开始累加概率）。
2. 定义骑士的移动方向：
   • 使用 dx 和 dy 数组来定义骑士的八个移动方向。
3. 动态规划计算概率：
   • 外层循环遍历每一步 K，从1到k。
   • 在每一步中，首先使用 memset 将 dp2（即下一步的概率数组）初始化为0。
   • 然后，遍历棋盘上的每一个位置 (i, j)，对于每个位置，遍历骑士的八个移动方向。
   • 计算骑士从当前位置 (i, j) 移动到下一个位置 (cx, cy) 的概率。如果 (cx, cy) 超出棋盘范围，则骑士“消失”在棋盘外，其概率为1（因为题目要求的是不在指定位置的概率，所以骑士离开棋盘也是一种“不在指定位置”的情况）。如果 (cx, cy) 在棋盘内，则概率是 pre[cx][cy] / 8，因为骑士有8种等可能的移动方式。
   • 将所有可能的移动概率累加到 cur[i][j] 中。
   • 交换 pre 和 cur 的指针，以便在下一步中使用新的概率数组。
4. 返回结果：
   • 经过 k 步后，pre[r][c] 存储的是骑士在 k 步后位于 (r, c) 的概率。
   • 因为题目要求的是不在 (r, c) 的概率，所以用 1 - pre[r][c] 来表示这个概率。

总结：

• 该代码通过动态规划的方法，逐步计算骑士在每一步移动后到达每个位置的概率。
• 通过交换 pre 和 cur 数组，实现了在每一步中基于前一步的概率来计算当前步的概率。
• 最终返回的是骑士在 k 步后不在指定位置 (r, c) 的概率。

原文地址：https://blog.csdn.net/m0_69493801/article/details/144313418

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！