牛客4580题解：动态规划求解网格路径概率问题（C++代码实现）

一、题目解读

牛客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数组标记障碍物，避免了无效路径的计算，而边界条件的特殊处理保证了概率推导的正确性。该解法具有清晰逻辑和良好可扩展性，适用于类似网格路径概率问题。