# Unique Paths II

## Unique Paths with obstacle

`1 * n`

matrix

there will be `0`

unique path on the left side of an obstacle.

```
+---+---+---+---+---+---+---+
| 1 | 1 | 1 | B | 0 | 0 | 0 |
+---+---+---+---+---+---+---+
```

obstacle blocks the path to girds on its bottom or left.

```
+---+---+---+---+---+---+---+
| 1 | 1 | 1 | B | 0 | 0 | 0 |
+---+---+---+---+---+---+---+
| 1 | 2 | | | | | |
+---+---+---+---+---+---+---+
| 1 | | | | B | | |
+---+---+---+---+---+---+---+
| 1 | | | n | x | | |
+---+---+---+---+---+---+---+
| 1 | | | | | | |
+---+---+---+---+---+---+---+
| 1 | | | | | | |
+---+---+---+---+---+---+---+
```

in this case, `gird x`

has only n paths from left grid.

Generally, `[x][y] = ([x - 1][y] or 0 if blocked) + ([x][y - 1] or 0 if blocked)`

### Source code *Read on Github*

```
1 public class Solution {
2 public int uniquePathsWithObstacles(int[][] obstacleGrid) {
3 // Note: The Solution object is instantiated only once and is reused by each test case.
4 int mx = obstacleGrid.length;
5 int my = obstacleGrid[0].length;
6
7 if(obstacleGrid[0][0] == 1) return 0;
8 if(obstacleGrid[mx - 1][my - 1] == 1) return 0;
9
10 int x, y;
11
12 boolean blocked = false;
13 for(x = 1; x < mx ; x++){
14 if (obstacleGrid[x][0] == 1) blocked = true;
15 obstacleGrid[x][0] = blocked ? 0 : 1;
16 }
17
18 blocked = false;
19 for(y = 1; y < my ; y++){
20 if (obstacleGrid[0][y] == 1) blocked = true;
21 obstacleGrid[0][y] = blocked ? 0 : 1;
22 }
23
24
25 obstacleGrid[0][0] = 1;
26
27
28 for(x = 1; x < mx ; x++){
29 for(y = 1; y < my; y++){
30 if(obstacleGrid[x][y] == 1)
31 obstacleGrid[x][y] = 0;
32 else
33 obstacleGrid[x][y] = obstacleGrid[x - 1][y] + obstacleGrid[x][y - 1];
34 }
35 }
36
37 return obstacleGrid[mx - 1][my - 1];
38
39 }
40 }
```