063 - Unique Paths II

Unique Paths II

Follow up for "Unique Paths":
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.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.
Note: m and n will be at most 100.
Hide Tags
Array Dynamic Programming
Hide Similar Problems
(M) Unique Paths


在062的基础上加了障碍物，也就是到这个点上的路径数目将直接置成0，

所以直接在062的代码上加个判断就好了。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int rst=0;
        int m=obstacleGrid.size();
        if(m)
        {
            int n=obstacleGrid[0].size();
            if(n)
            {
                int* matrix = new int[m*n];
                memset(matrix, 0, m*n*sizeof(int));

                matrix[(m-1)*n + n-1]=1;
                for(int ii=m-1; ii>=0; ii--)
                {
                    for(int jj=n-1; jj>=0; jj--)
                    {
                        int idx = (ii)*n + jj;

                        if(obstacleGrid[ii][jj])
                            matrix[idx] = 0;
                        else
                        {
                            if(jj<n-1)
                                matrix[idx] += matrix[idx+1];
                            if(ii<m-1)
                                matrix[idx] += matrix[idx+n];
                        }
                    }
                }
                rst = matrix[0];
                if(matrix)
                    delete[] matrix;            }
        }
        return rst;
    }
};

4 ms.