A man is located at the top-left corner of a mxn  grid .

he can only move either down or right at any point in time. he has to reach the bottom-right corner of the grid

How many possible unique paths are there?

An obstacle and space is marked as 1 and 0 respectively in the grid.

its better to try  Unique Paths I first , than solve this problem

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

method 2 :

using dynamic programming

c++ implementation:

```int uniquePathsWithObstacles(vector<vector<int>>& g) {
int m=g.size();
int n=g.size();
int dp[m][n];
if(g==1)
return 0;
dp=1;
for(int i=1;i<m;i++)
{
if(g[i]==1 ||dp[i-1]==0)
dp[i]=0;
else
dp[i]=1;
}
for(int j=1;j<n;j++)
{
if(g[j]==1|| dp[j-1]==0)
dp[j]=0;
else
dp[j]=1;
}

for(int i=1;i<m;i++)
{
for(int j=1;j<n;j++)
{
if(g[i][j]==1)
dp[i][j]=0;
else
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}

return dp[m-1][n-1];

}```

Time Complexity: O(mxn)
space Complexity: O(mxn)

darkmode