学步园

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.

思路：这也是一道DP的题，在unique paths上设置了路径障碍。可用数组ob[m][n]=-1表示在点(m,n)有障碍不能通过，则到达该点的路径数f[m][n]=0。边界条件是当m=0||n=0时，f[m][n]=0，当m=1&&n=1&&ob[m][n]!=-1时，才能到达点(m,n)有一条路径，状态转移公式同I。

class Solution {
private:
    int ob[101][101];
    int f[101][101];
public:
    int unique(int m, int n)
    {
        if (ob[m][n] == -1)
        {
            return 0;
        }    
        if (m==0 || n==0)
        {
            return 0;
        }  
        if (m == 1 && n == 1 && ob[m][n] != -1)
        {
            f[m][n] = 1;
            return 1;
        }         
        if (ob[m][n] != -1 && f[m][n] != 0)
        {
            return f[m][n];
        }   
        f[m][n] = unique(m-1,n) + unique(m, n-1);
        return f[m][n];
    }    
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        memset(ob, 0, sizeof(ob));
        memset(f, 0, sizeof(f));
        int m = obstacleGrid.size(),i,j;
        if (m == 0)
        {
            return 0;
        }    
        int n = obstacleGrid[0].size();
        for(i=0; i<m; ++i)
         for(j=0; j<n; ++j)
           if(obstacleGrid[i][j] == 1)
         {
             ob[i+1][j+1] = -1;
         }  
        return unique(m, n);   
    }
};