动态规划路径问题

理解问题情况

用户的问题是，给定一个N x N的网格，起点为(1,1)，终点为(N,N)，移动只能向右或向下。网格中有M个障碍，不能通过这些单元格。起点和终点都不受障碍影响。障碍可能有重复坐标，计算从起点到终点的不同路径数。

考虑障碍影响

在路径总数大时，障碍物会显著减少通路。使用动态规划计算每个点的通路数，忽略障碍物。

标记障碍物

最重要的是确保只访问一个前一个单元格，并且避免障碍物重复。使用集合或布尔网格标记障碍物。

提交C++代码

规划网格路径

初始化一个大小为N+1xN+1的网格，并标记障碍。通过动态规划，计算出从起点到目标点的路径数。

初始化动态规划表

正在整理测试代码，确保样本输入与输出相符。初始化DP表为0。继续推进。

更新动态规划表格

我正在通过逐格计算来更新DP表格。障碍物被设为0，其他格子通过前面格子的和来填充。最终，我找到了满足条件的路径数。

设计代码大纲

我正在设计代码大纲，处理障碍物和边界条件，确保有效的路径规划。

To solve this problem, we will use dynamic programming. We'll create a 2D array dp where dp[i][j] represents the number of ways to reach cell (i, j) from (1, 1). Since we can only move right or down, we can calculate dp[i][j] based on the values of dp[i-1][j] and dp[i][j-1], unless the cell (i, j) is an obstacle.

Below is the C++ code that implements this logic:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    vector<vector<bool>> obstacle(N + 1, vector<bool>(N + 1, false));
    for (int i = 0; i < M; ++i) {
        int x, y;
        cin >> x >> y;
        obstacle[x][y] = true;
    }

    vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, 0));
    dp[1][1] = 1; // Starting point

    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (obstacle[i][j]) {
                dp[i][j] = 0;
            } else if (!(i == 1 && j == 1)) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }

    cout << dp[N][N] << endl;

    return 0;
}

Explanation:

We read the grid size N and the number of obstacles M.
We create a 2D boolean array obstacle to mark the positions of the obstacles.
We initialize the dp array with zeros and set dp[1][1] to 1 since there's only one way to be at the starting position.
We iterate through each cell in the grid:
- If the current cell is an obstacle, we set dp[i][j] to 0.
- If it's not the starting cell, we calculate the number of ways to reach it by summing the ways to reach the cell above it and the cell to the left of it.
Finally, we output the value of dp[N][N], which is the number of ways to reach the bottom-right corner.

Sample Input:

3 1
3 1

Sample Output:

This output matches the expected result as per the problem description.

动态规划路径问题

Вопрос

Мысль

Ответ

Поделиться этим Q&A