Sunday, May 5, 2013

Leetcode: Unique Paths II in C++



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.
Solution:

int help(int m, int n, vector<vector<int> >& obstacleGrid, vector<vector<int> >& result)
    {
        if(result[m][n]!=-1)
        {
            return result[m][n];
        }
        result[m][n] = 0;
        if(obstacleGrid[m-1][n-1]==1)
        {
            return 0;
        }
        if(m>1)
        result[m][n] += help(m-1,n,obstacleGrid, result);
        if(n>1)
        result[m][n] += help(m,n-1,obstacleGrid ,result);
        return result[m][n];
    }
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        if(obstacleGrid.size()==0)
        return 0;
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int> > result(m+1, vector<int>(n+1, -1));
        if(obstacleGrid[0][0]==0)
        {
            result[1][1] =  1;
        }
        else
            result[1][1] =  0;
        help(m, n, obstacleGrid, result);
        return result[m][n];
    }

No comments:

Post a Comment