牛客4580题解：动态规划求解网格路径概率问题（C++代码实现）
3个月前 (06-23)
一、题目解读
牛客4580题要求在一个n×m的网格中计算从起点(1,1)到终点(n,m)的概率。网格中存在障碍物（标记为坏点），路径只能向右或向下移动。到达终点时，若处于边界位置，概率转移规则不同：下边界时向右概率为0.5，右边界时向下概率为0.5，普通位置则各方向概率均为0.5。题目需要输出最终到达终点的概率，保留两位小数。
二、解题思路
该题目采用动态规划（DP）求解。核心思想是将问题分解为子问题，通过递推计算每个位置到达终点的概率。定义状态dp[i][j]为从起点到位置(i,j)的概率。根据路径规则，每个位置的概率由上方和左方位置的概率推导而来，需特殊处理边界和障碍物情况。通过遍历网格，逐步更新状态值，最终得到终点概率。
三、解题步骤
1. 输入处理：读取网格大小n、m及坏点数量k，标记坏点位置（bad数组）。
2. 初始化：起点概率dp[1][1]设为1，其他位置初始为0。
3. 状态转移：
○ 若当前位置为坏点，概率置0；
○ 若为终点，概率由上方和左方概率相加；
○ 若为下边界，上方概率1 + 左方概率0.5；
○ 若为右边界，上方概率 + 左方概率*0.5；
○ 普通位置则上方0.5 + 左方0.5。
4. 输出结果：固定小数点后两位输出dp[n][m]。
四、代码和注释
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
int main() {
int n, m, k;
while (cin >> n >> m >> k) { // 处理多组数据
vector<vector<bool>> bad(n+1, vector<bool>(m+1, false)); // 标记坏点
vector<vector<double>> dp(n+1, vector<double>(m+1, 0.0)); // 概率DP数组
// 标记蘑菇位置
while (k--) {
int x, y;
cin >> x >> y;
bad[x][y] = true; // 标记为坏点
}
dp[1][1] = 1.0; // 起点概率为1
for (int i = 1; i <= n; ++i) { // 行遍历
for (int j = 1; j <= m; ++j) { // 列遍历
if (i == 1 && j == 1) continue; // 跳过起点
if (bad[i][j]) { // 坏点概率置0
dp[i][j] = 0.0;
continue;
}
// 处理边界情况
if (i == n && j == m) { // 终点
dp[i][j] = dp[i-1][j] + dp[i][j-1];
} else if (i == n) { // 下边界
dp[i][j] = dp[i-1][j] * 0.5 + dp[i][j-1];
} else if (j == m) { // 右边界
dp[i][j] = dp[i-1][j] + dp[i][j-1] * 0.5;
} else { // 普通位置
dp[i][j] = dp[i-1][j] * 0.5 + dp[i][j-1] * 0.5;
}
}
}
cout << fixed << setprecision(2) << dp[n][m] << endl; // 输出终点概率
}
return 0;
}五、总结
本题关键在于动态规划的状态定义与边界条件的处理。通过明确概率转移规则，结合网格遍历，高效计算出终点概率。代码中利用bad数组标记障碍物，避免了无效路径的计算，而边界条件的特殊处理保证了概率推导的正确性。该解法具有清晰逻辑和良好可扩展性，适用于类似网格路径概率问题。
原创内容 转载请注明出处
