## The challenge

On a 2-dimensional `grid`, there are 4 types of squares:

• `1` represents the starting square.  There is exactly one starting square.
• `2` represents the ending square.  There is exactly one ending square.
• `` represents empty squares we can walk over.
• `-1` represents obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

Example 1:

```Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)```

Example 2:

```Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)```

Example 3:

```Input: [[0,1],[2,0]]
Output: 0
Explanation:
There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.
```

Note:

1. `1 <= grid.length * grid[0].length <= 20`

## The solution in Java

This solution uses Depth First Search to come to an answer.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 `````` ``````class Solution { public int uniquePathsIII(int[][] grid) { /* 1 = start 2 = end 0 = empty -1 = obstacle [ [1,0,0,0], [0,0,0,0], [0,0,2,-1] ] */ // start `x` int sx = 0; // start `y` int sy = 0; // start `zero` int zero = 0; // loop through grid columns for(int r = 0; r= grid.length || y >= grid[0].length || grid[x][y] == -1){ return 0; } // if end, return if(grid[x][y] == 2) { return zero == -1 ? 1 : 0; } // set current points to obstacle / something we can't go over again grid[x][y] = -1; // decrement the amount of zeros zero--; // recurse in all directions int totalPaths = dfs(grid, x+1, y, zero) + dfs(grid, x, y+1, zero) + dfs(grid, x-1, y, zero) + dfs(grid, x, y-1, zero); // set to a path grid[x][y] = 0; // increment the amount of zeros zero++; // return the amount of paths return totalPaths; } } ``````