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.0
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 <= grid.length * grid[0].length <= 20
The solution in Java
This solution uses Depth First Search to come to an answer.
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; r++) { // loop through grid's first row for(int c = 0; c<grid[0].length; c++) { // find where the starting point is if(grid[r] == 1){ sx = r; sy = c; // otherwise count the zeros } else if(grid[r] == 0) zero++; } } // return from Depth First Search return dfs(grid, sx, sy, zero); } // dfs = Depth First Search private int dfs(int[][] grid, int x, int y, int zero) { // if out of bounds, return if( x < 0 || y < 0 || x >= 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; } }