UniquePath

class Solution {

  int ROWS = 0;
  int COLS = 0;

  public int uniquePathsIII(int[][] grid) {
    ROWS = grid.length;
    COLS = grid[0].length;

    int startRow = 0;
    int startCol = 0;
    int nonObstaclesCount = 0;

    // find start position and count non obstacles count
    for (int r = 0; r < ROWS; r++) {
      for (int c = 0; c < COLS; c++) {
        if (grid[r][c] != -1) {
          nonObstaclesCount++;

          if (grid[r][c] == 1) {
            startRow = r;
            startCol = c;
          }
        }
      }
    }

    return backtrack(grid, startRow, startCol, nonObstaclesCount);
  }

  private int backtrack(int[][] grid, int row, int col, int remaining) {
    // if grid is end
    if (grid[row][col] == 2) {
      // if only end square left, count the valid path
      if (remaining == 1) {
        return 1;
      }

      return 0;
    }

    // mark visited
    int tmp = grid[row][col];
    grid[row][col] = -4;

    int[][] directions = {
      {-1, 0}, // up
      {0, 1},  // right
      {1, 0},  // down
      {0, -1}  // left
    };

    int countPath = 0;

    for (int i = 0; i < 4; i++) {
      int[] direction = directions[i];

      int nextRow = row + direction[0];
      int nextCol = col + direction[1];

      // out of bound
      if (nextRow < 0 || nextRow >= ROWS || nextCol < 0 || nextCol >= COLS) {
        continue;
      }

      // if grid is visited (-4) or is an obstacles (-1), there is no valid path continue
      if (grid[nextRow][nextCol] < 0) {
        continue;
      }

      countPath += backtrack(grid, nextRow, nextCol, remaining - 1);
    }

    grid[row][col] = tmp;

    return countPath;
  }
}