# leetocde 63. Unique Paths II

Posted by 111qqz on Tuesday, April 11, 2017

## TOC

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`.

``````/* ***********************************************
Author :111qqz
Created Time :2017年04月11日 星期二 18时37分47秒
File Name :63.cpp
************************************************ */
class Solution {
public:
int n,m;
void pr(vector<vector<int> > & a)
{
for ( int i = 0 ; i < n ; i++)
for ( int j = 0 ;j < m ; j++)
printf("%d%c",a[i][j],j==m-1?'\n':' ');
}
int uniquePathsWithObstacles(vector<vector<int>>& maze) {
n = maze.size();
m = maze[0].size();
vector<vector<int> >dp(n,vector<int>(m,0));
for ( int i = 0 ;  i < n ; i++)
{
if (sad) dp[i][0] = 0 ;
else dp[i][0] = 1;
}
for ( int j = 0 ; j < m ; j++)
{
if (sad) dp[0][j] = 0 ;
else dp[0][j] = 1;
}
//	pr(dp);
for ( int i = 1 ; i < n ;  i++)
{
for (  int j = 1 ; j < m ; j++)
{
if (maze[i][j]==1) dp[i][j]=0;
else dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
//	pr(dp);
return dp[n-1][m-1];
}
};
``````

「真诚赞赏，手留余香」