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];}

解题思路：

初始化动态规划数组：
- 使用两个二维数组 dp1 和 dp2 来存储每一步移动后的概率。dp1 用于存储当前步的概率，dp2 用于存储下一步的概率。
- 使用 memset 函数将 dp1 初始化为0，因为初始时骑士还未移动，所以所有位置的概率都是0（但这里实际上是为了后续计算方便，初始值对结果无影响，因为我们会从1开始累加概率）。
定义骑士的移动方向：
- 使用 dx 和 dy 数组来定义骑士的八个移动方向。
动态规划计算概率：
- 外层循环遍历每一步 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 的指针，以便在下一步中使用新的概率数组。
返回结果：
- 经过 k 步后，pre[r][c] 存储的是骑士在 k 步后位于 (r, c) 的概率。
- 因为题目要求的是不在 (r, c) 的概率，所以用 1 - pre[r][c] 来表示这个概率。