牛客4580题解：网格路径概率的动态规划计算
一、问题描述
牛客4580题要求计算在n×m网格中，从左上角(1,1)到右下角(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));
// dp数组存储到达每个格点的概率
vector<vector<double>> dp(n+1, vector<double>(m+1, 0.0));
// 读取并标记蘑菇位置
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;
}
}
}
// 输出结果保留2位小数
cout << fixed << setprecision(2) << dp[n][m] << endl;
}
return 0;
}四、关键点解析
数据结构选择：
二维bool数组标记蘑菇位置
二维double数组存储概率值
边界处理：
下边界只能从上方来
右边界只能从左方来
终点可以从上方或左方来
概率计算：
普通位置：两种移动方向各占50%概率
边界位置：唯一移动方向概率为100%
蘑菇位置：概率直接置0
五、常见问题解答
Q: 为什么起点概率初始化为1？ A: 因为起点是确定的，所以到达概率为100%
Q: 时间复杂度是多少？ A: O(n×m)，需要填充整个n×m的DP表
Q: 如何处理大网格情况？ A: 可以优化空间复杂度，只保留当前行和上一行的数据
原创内容 转载请注明出处
