用c++完成题目描述 有一个机器人位于一个nxm 个网格左上角。机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。现在考虑网格中有障碍物，那样将会有多少条不同的路径?网格中的障碍和空位置分别月

在C++中，解决这个问题通常可以使用动态规划(Dynamic Programming)的方法，特别是经典的宽度优先搜索(Breadth First Search, BFS)或递归回溯加上记忆化技术。我们可以创建一个二维数组dp，其中dp[i][j]表示从左上角到达网格位置(i, j)的不同路径数，遇到障碍则dp[i][j]为0。

算法步骤大致如下：

1. 初始化：dp[0][0] = 1 (起点只有一个路径)，其他边界条件dp[i][0], dp[0][j] (i > 0 或 j > 0)都设为0，因为无法到达那里。

2. 动态更新：对于每个网格位置(i, j)，如果当前位置不是障碍，则考虑两个相邻的未访问位置(i+1, j)和(i, j+1)。如果这两个位置都是空格，那么到达它们的路径数就是到达前一个位置的路径数加一。

int m, n;
bool grid[n][m]; // 网格，grid[i][j] 表示位置 (i, j) 是否有障碍

for (int i = 1; i < n; ++i)
{
    for (int j = 1; j < m; ++j)
    {
        if (!grid[i][j]) // 非障碍位置
        {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
        else
        {
            dp[i][j] = 0; // 遇到障碍，路径数为0
        }
    }
}

3. 最终结果：返回dp[n-1][m-1]即为目标位置的路径数。