63. Unique Paths II

problem description

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

algorithm thought

这题和上一题唯一的区别就是，这里在机器人的行动路上放了一些障碍。其实和上题做法没什么区别，当当前走到障碍的时候，直接把这个位置的结果赋值0。这样的好处是，既可以代表这里没有一种方案可以走到，也可以在他右边和下面得到总线路时，加上的是0。

code

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        for(int i=0;i<obstacleGrid[0].size();++i){
            if(obstacleGrid[0][i]==1)
                for(;i<obstacleGrid[0].size();++i)
                    obstacleGrid[0][i]=0;
            else
                obstacleGrid[0][i]=1;
        }
        //obstacleGrid[0][0]=0;
        for(int i=1;i<obstacleGrid.size();++i){
            if(obstacleGrid[i][0]==1||obstacleGrid[0][0]==0)
                for(;i<obstacleGrid.size();++i)
                    obstacleGrid[i][0]=0;
            else
                obstacleGrid[i][0]=1;
        }
        for(int i=1;i<obstacleGrid.size();++i){
            for(int j=1;j<obstacleGrid[0].size();++j){
                if(obstacleGrid[i][j]==1)
                    obstacleGrid[i][j]=0;
                else
                    obstacleGrid[i][j]=obstacleGrid[i-1][j]+obstacleGrid[i][j-1];
            }
        }
        return obstacleGrid.back().back();
    }
};

algorithm analysis

相比于上题加入了一些处理，但是时间复杂度还是O(n²)