## Algorithm

Problem Name: 63. Unique Paths II

You are given an `m x n` integer array `grid`. There is a robot initially located at the top-left corner (i.e., `grid[0][0]`). The robot tries to move to the bottom-right corner (i.e., `grid[m - 1][n - 1]`). The robot can only move either down or right at any point in time.

An obstacle and space are marked as `1` or `0` respectively in `grid`. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to `2 * 109`.

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

Constraints:

• `m == obstacleGrid.length`
• `n == obstacleGrid[i].length`
• `1 <= m, n <= 100`
• `obstacleGrid[i][j]` is `0` or `1`.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>

int uniquePathsWithObstacles(int **obstacleGrid, int m, int n){
int (*p)[n] = (int (*)[n]) calloc(m * n, sizeof(int));
p[0][0] = 1;
int i, j;
for (i = 0; i  <  m; i++) {
for (j = 0; j  <  n; j++) {
if (obstacleGrid[i][j]) {
p[i][j] = 0;
}
else {
if (i > 0 && j == 0)
p[i][j] = p[i - 1][j];
if (j > 0 && i == 0)
p[i][j] = p[i][j - 1];
if (i > 0 && j > 0)
p[i][j] = p[i][j - 1] + p[i - 1][j];
}
}
}

return p[m - 1][n - 1];
}

int main(){
int m, n, i;
m = n = 3;
int **obstacleGrid = (int **) calloc (m, sizeof(int *));

for (i = 0; i  <  m; i++)
obstacleGrid[i] = (int *) calloc (n, sizeof(int));

obstacleGrid[1][1] = 1;

printf("%d\n", uniquePathsWithObstacles(obstacleGrid, m, n));
return 0;
}
``````
Copy The Code &

Input

cmd
obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

Output

cmd
2

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
vector<int>dp(n);
dp[0] = 1;
for (int i = 0; i  <  m; ++i) {
for (int j = 0; j  <  n; ++j) {
if (obstacleGrid[i][j] == 1) {
dp[j] = 0;
} else {
dp[j] += dp[j - 1];
}
}
}
return dp[n - 1];
}
};
``````
Copy The Code &

Input

cmd
obstacleGrid = [[0,1],[0,0]]

Output

cmd
1

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];

for (int i=0; i < dp.length; i++) {
if (obstacleGrid[i][0] == 1) {
break;
}
dp[i][0] = 1;
}

for (int i=0; i < dp[0].length; i++) {
if (obstacleGrid[0][i] == 1) {
break;
}
dp[0][i] = 1;
}

for (int i=1; i < dp.length; i++) {
for (int j=1; j < dp[0].length; j++) {
if (obstacleGrid[i][j] != 1) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}

return dp[obstacleGrid.length-1][obstacleGrid[0].length-1];
}
}
``````
Copy The Code &

Input

cmd
obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

Output

cmd
2

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const uniquePathsWithObstacles = function(obstacleGrid) {
const rows = obstacleGrid.length
const cols = obstacleGrid[0].length
const dp = Array.from({ length: rows }, () => new Array(cols).fill(0))
if (obstacleGrid[0][0] === 1) return 0
else dp[0][0] = 1
let firstRowOneIdx
let firstColOneIdx
for (let i = 0; i  <  cols; i++) {
if (obstacleGrid[0][i] === 1) {
firstRowOneIdx = i
break
} else {
dp[0][i] = 1
}
}
for (let i = 0; i  <  rows; i++) {
if (obstacleGrid[i][0] === 1) {
firstColOneIdx = i
break
} else {
dp[i][0] = 1
}
}

for (let i = 1; i  <  rows; i++) {
for (let j = 1; j  <  cols; j++) {
if (obstacleGrid[i][j] !== 1) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
}
}
}
return dp[rows - 1][cols - 1]
}
``````
Copy The Code &

Input

cmd
obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

Output

cmd
2

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid):
if obstacleGrid[0][0] == 1: return 0
for i in range(len(obstacleGrid)):
for j in range(len(obstacleGrid[0])):
if obstacleGrid[i][j] == 1 or i == j == 0:
obstacleGrid[i][j] -= 1
else:
add1 = obstacleGrid[i - 1][j] if i > 0 else 0
add2 = obstacleGrid[i][j - 1] if j > 0 else 0
return abs(obstacleGrid[-1][-1])
``````
Copy The Code &

Input

cmd
obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

Output

cmd
2

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _063_UniquePaths2
{
public int UniquePathsWithObstacles(int[,] obstacleGrid)
{
var rowLenght = obstacleGrid.GetLength(0);
var columnLenght = obstacleGrid.GetLength(1);

if (rowLenght  < = columnLenght)
{
var possiblePath = new int[rowLenght];
possiblePath[0] = obstacleGrid[0, 0] == 0 ? 1 : 0;

for (int i = 0; i  <  columnLenght; i++)
for (int j = 0; j  <  rowLenght; j++)
possiblePath[j] = obstacleGrid[j, i] == 1
? 0
: j != 0 ? possiblePath[j - 1] + possiblePath[j] : possiblePath[j];

return possiblePath[rowLenght - 1];
}
else
{
var possiblePath = new int[columnLenght];
possiblePath[0] = obstacleGrid[0, 0] == 0 ? 1 : 0;

for (int i = 0; i  <  rowLenght; i++)
for (int j = 0; j  <  columnLenght; j++)
possiblePath[j] = obstacleGrid[i, j] == 1
? 0
: j != 0 ? possiblePath[j - 1] + possiblePath[j] : possiblePath[j];

return possiblePath[columnLenght - 1];
}
}
}
}
``````
Copy The Code &

Input

cmd
obstacleGrid = [[0,1],[0,0]]

Output

cmd
1