Unique Paths III

LeetCode Q 980 - Unique Paths III

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:

• (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(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: [[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

Code:

private static final int[] DIRS = {-1, 0, 1, 0, -1};
private int res = 0;
public int uniquePathsIII(int[][] grid) {
  
  int R = grid.length, C = grid[0].length;
  int zeros = 0, startX = 0, startY = 0, endX = 0, endY = 0;
  
  for (int r = 0; r < R; r++) {
    for (int c = 0; c < C; c++) {
      if (grid[r][c] == 0) zeros++;
      if (grid[r][c] == 1) { startX = r; startY = c; }
      if (grid[r][c] == 2) { endX = r; endY = c; }
    }
  }
  
  backtrack(grid, startX, startY, endX, endY, 0, zeros);

  return res;
}

private void backtrack(int[][] grid, int currX, int currY, 
                     int endX, int endY, int count, int zeros) {
  if (currX == endX && currY == endY && count == zeros + 1) {
    res++; return;
  }
  
  for (int i = 0; i < 4; i++) {
    int nx = currX + DIRS[i], ny = currY + DIRS[i + 1];
    if (nx < 0 || ny < 0 || nx >= grid.length || ny >= grid[0].length || grid[nx][ny] == -1 || grid[nx][ny] == 1) continue;
    
    int ori = grid[nx][ny];
    grid[nx][ny] = -1; count++;
    backtrack(grid, nx, ny, endX, endY, count, zeros);
    grid[nx][ny] = ori; count--;
  }
}