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
-
Method 1: dfs AC 99.91%
- this is a quite normal search question.
class Solution { private int res = 0; public int uniquePathsIII(int[][] grid) { int height = grid.length, width = grid[0].length; int count = 0; int[] start = null, end = null; for(int i = 0; i < height; i++){ for(int j = 0; j < width; j++){ if(grid[i][j] == 1) start = new int[]{i, j}; else if(grid[i][j] == 0) count++; } } boolean[][] visited = new boolean[height][width]; visited[start[0]][start[1]] = true; dfs(grid, start[0], start[1], visited, count + 1); return this.res; } private void dfs(int[][] grid, int row, int col, boolean[][] visited, int count){ if(grid[row][col] == 2 && count == 0) this.res++; else{ int tempRow = 0, tempCol = 0; for(int d = 0; d < 4; d++){ tempRow = row + dir[d][0]; tempCol = col + dir[d][1]; if(tempRow >= 0 && tempRow < grid.length && tempCol >= 0 && tempCol < grid[0].length && !visited[tempRow][tempCol] && grid[tempRow][tempCol] != -1){ visited[tempRow][tempCol] = true; dfs(grid, tempRow, tempCol, visited, count - 1); visited[tempRow][tempCol] = false; } } } } }
-
Method 2: dp Hamilton path
- dp[x][y][state]: (x, y) is current position and state is a bit map shows rest of the points to visit.
- State transfer function:
- dp[x][y][state] = dp[tx][ty][unset_neighbour(state)], for all neighbours
- (x, y) is the starting point, it must go through its neighbour to reach the destination.
- the total ways equals the sum of all its neighbours ways to reach the destination.
- dp[x][y][state] = dp[tx][ty][unset_neighbour(state)], for all neighbours
- Result: dfs(startX, startY, all points needs to be visited state);
class Solution { private int height, width; private short[][][] dp = null; private static int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; public int uniquePathsIII(int[][] grid) { height = grid.length; width = grid[0].length; int[] start = null; dp = new short[height][width][1 << (width * height)]; int state = 0; for(int i = 0; i < height; i++){ for(int j = 0; j < width; j++){ if(grid[i][j] == 0 || grid[i][j] == 2) state |= key(i, j); else if(grid[i][j] == 1) start = new int[]{i, j}; } } return dfs(grid, start[0], start[1], state); } private int key(int i, int j){ return 1 <<(i * width + j); } private int dfs(int[][] grid, int i, int j, int state){ if(dp[i][j][state] > 0) return dp[i][j][state]; if(grid[i][j] == 2 && state == 0) return 1; int tempRow = 0, tempCol = 0; for(int d = 0; d < 4; d++){ tempRow = i + dir[d][0]; tempCol = j + dir[d][1]; if(tempRow >= 0 && tempRow < height && tempCol >= 0 && tempCol < width && grid[tempRow][tempCol] != -1){ if((state & key(tempRow, tempCol)) == 0) continue; dp[i][j][state] += dfs(grid, tempRow, tempCol, (state ^ key(tempRow, tempCol))); } } return dp[i][j][state]; } }
-
Method 1: dfs
class Solution { private int height; private int width; private int res; private static final int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; public int uniquePathsIII(int[][] grid) { height = grid.length; width = grid[0].length; int count = 0; int startX = -1, startY = -1; for(int i = 0; i < height; i++){ for(int j = 0; j < width; j++){ if(grid[i][j] == 1){ startX = i; startY = j; }else if(grid[i][j] == 0) count++; } } boolean[][] visited = new boolean[height][width]; visited[startX][startY] = true; dfs(startX, startY, grid, count, visited); return this.res; } private void dfs(int row, int col, int[][] grid, int count, boolean[][] visited){ if(count == -1 && grid[row][col] == 2) this.res++; else{ int tx = 0, ty = 0; for(int d = 0; d < 4; d++){ tx = row + dir[d][0]; ty = col + dir[d][1]; if(tx >= 0 && tx < height && ty >= 0 && ty < width && !visited[tx][ty] && grid[tx][ty] != -1){ visited[tx][ty] = true; dfs(tx, ty, grid, count - 1, visited); visited[tx][ty] = false; } } } } }
-
Method 2:dp
class Solution { private int height; private int width; private int[][] dp; private static final int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; public int uniquePathsIII(int[][] grid) { this.height = grid.length; this.width = grid[0].length; this.dp = new int[height * width][1 << (height * width)]; int startX = -1, startY = -1; int state = 0; for(int i = 0; i < height; i++){ for(int j = 0; j < width; j++){ if(grid[i][j] == 0 || grid[i][j] == 2) state |= (1 << (i * width) + j); else if(grid[i][j] == 1){ startX = i; startY = j; } } } return dfs(grid, startX, startY, state); } private int dfs(int[][] grid, int row, int col, int state){ if(dp[row * width + col][state] > 0) return dp[row * width + col][state]; if(state == 0 && grid[row][col] == 2) return 1; int tx = 0, ty = 0; for(int d = 0; d < 4; d++){ tx = row + dir[d][0]; ty = col + dir[d][1]; if(tx >= 0 && tx < height && ty >= 0 && ty < width && grid[tx][ty] != -1){ if((state & (1 << (tx * width + ty))) == 0) continue; dp[row * width + col][state] += dfs(grid, tx, ty, state ^ (1 << (tx * width + ty))); } } return dp[row * width + col][state]; } }