LeetCode [980] Unique Paths III

 980. Unique Paths III

Hard

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. 1 <= grid.length * grid[0].length <= 20

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

class Solution { int m, n, b=0; int ways = 0; int[][] dirs = new int[][]{{1,0},{-1,0},{0,-1},{0,1}}; public int uniquePathsIII(int[][] grid) { m = grid.length; n = grid[0].length; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(grid[i][j]==-1) b++; } } for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(grid[i][j]==1) dfs(i, j, grid, 1); } } return ways; } void dfs(int i, int j, int[][] grid, int len){ if(grid[i][j]==2){ if(len == m*n-b) ways++; }else{ for(int[] d : dirs){ int ii = i+d[0]; int jj = j+d[1]; if(ii>=0 && ii<m && jj>=0 && jj<n && (grid[ii][jj]==0||grid[ii][jj]==2)){ int t = grid[ii][jj]; if(t==0) grid[ii][jj] = -1; dfs(ii, jj, grid, len+1); grid[ii][jj] = t; } } } } }