牛客4580题解：网格路径概率的动态规划计算

一、问题描述

牛客4580题要求计算在n×m网格中，从左上角(1,1)到右下角(n,m)的移动路径概率。网格中存在若干蘑菇位置(不可经过)，每次只能向右或向下移动，求成功到达终点的概率。

二、算法核心思想

使用动态规划记录到达每个格点的概率：

1. 标记所有蘑菇位置

2. 初始化起点概率为1

3. 根据边界条件递推计算每个格点概率

4. 考虑普通格点、边界格点和终点的不同转移方式

三、完整代码实现（带注释）

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

四、关键点解析

1. 数据结构选择：

• 二维bool数组标记蘑菇位置

• 二维double数组存储概率值

2. 边界处理：

• 下边界只能从上方来

• 右边界只能从左方来

• 终点可以从上方或左方来

3. 概率计算：

• 普通位置：两种移动方向各占50%概率

• 边界位置：唯一移动方向概率为100%

• 蘑菇位置：概率直接置0

五、常见问题解答

Q: 为什么起点概率初始化为1？ A: 因为起点是确定的，所以到达概率为100%

Q: 时间复杂度是多少？ A: O(n×m)，需要填充整个n×m的DP表

Q: 如何处理大网格情况？ A: 可以优化空间复杂度，只保留当前行和上一行的数据