Question

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

Solution:

  • 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.
    • Result: dfs(startX, startY, all points needs to be visited state); 
        class Solution {
  private int height, width;
  private short[][][] dp = null;       
  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];
  }
  }

Reference

  1. 花花酱 LeetCode 980. Unique Paths III