63. Unique Paths II ---------M

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 109.

 

Example 1:

Input: obstacleGrid = [[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

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

 

Constraints:

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] is 0 or 1.

A:

*************************  第二遍， 1D array *****************************
 Using 2个。1D array to save the status after visiting each row

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<int> line(n,0);
        line[0] = 1 - obstacleGrid[0][0]; // set 0 if start point is occupied, otherwise 1
        for(int i =0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(obstacleGrid[i][j]== 1 ){
                    line[j] = 0;
                }else{
                    line[j] += (j==0)?0:line[j-1];
                }
            }
        }
        return line[n-1];
    }
};

其实可以更改进一步。 只用一个 1D array 就可以了

class Solution {

public:

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

int m = obstacleGrid.size(), n = obstacleGrid[0].size();

vector<int> V(n, 0);

int preVal = 1;

for (int j = 0; j < n; j++) {

if (obstacleGrid[0][j] == 1) {

preVal = 0;

}

V[j] = preVal;

}

preVal = V[0];

for (int i = 1; i < m; i++) {

for (int j = 0; j < n; j++) {

if (j == 0) {

if (obstacleGrid[i][j] == 1) {

preVal = 0;

}

V[j] = preVal;

} else {

if (obstacleGrid[i][j] == 1) {

V[j] = 0;

} else {

V[j] += V[j - 1];

}

}

}

}

return V[n - 1];

}

};

Mistakes:
假设的 第一个位置，不能是obctacle的情况，  是不对的

比较tricky的地方，就是A[1] = 1 - obstacleGrid[0][0];  这里是A[1]是为了设置初始状态