https://leetcode-cn.com/problems/unique-paths-ii/

image.png

思路

由于它添加了障碍，因此我们需要将有障碍的路径置为0，从而避开路障。

注意点

  • 将障碍的位置置为0
  • 我们需要考虑到边界也可能被堵塞的情况，不能直接设置 d[i][0]，d[0][j] 为1
  • 要想到 dp[0][0] 和 dp[m - 1][n - 1] 被堵死的情况
  1. class Solution {
  2. public:
  3.     int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
  4.         if(obstacleGrid.empty() || obstacleGrid[0].empty()) return 0;
  5.         int m = obstacleGrid.size();
  6.         int n = obstacleGrid[0].size();
  8.         vector<vector<int>> dp(m, vector<int>(n, 0));
  9.         for(int i = 0; i < m; i++) {
  10.             for(int j = 0; j < n; j++) {
  11.                 if(obstacleGrid[i][j] == 1) dp[i][j] = 0;
  12.                 else {
  13.                     if(i == 0 && j == 0) dp[i][j] = 1;
  14.                     else if(i == 0) dp[i][j] = dp[i][j - 1];
  15.                     else if(j == 0) dp[i][j] = dp[i - 1][j];
  16.                     else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  17.                 }
  18.             }
  19.         }
  20.         return dp[m - 1][n - 1];
  21.     }
  22. };