Guest User

UniquePath

a guest
Aug 22nd, 2021
81
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.  
  3.   int ROWS = 0;
  4.   int COLS = 0;
  5.  
  6.   public int uniquePathsIII(int[][] grid) {
  7.     ROWS = grid.length;
  8.     COLS = grid[0].length;
  9.    
  10.     int startRow = 0;
  11.     int startCol = 0;
  12.     int nonObstaclesCount = 0;
  13.    
  14.     // find start position and count non obstacles count
  15.     for (int r = 0; r < ROWS; r++) {
  16.       for (int c = 0; c < COLS; c++) {
  17.         if (grid[r][c] != -1) {
  18.           nonObstaclesCount++;
  19.          
  20.           if (grid[r][c] == 1) {
  21.             startRow = r;
  22.             startCol = c;
  23.           }
  24.         }
  25.       }
  26.     }
  27.    
  28.     return backtrack(grid, startRow, startCol, nonObstaclesCount);
  29.   }
  30.  
  31.   private int backtrack(int[][] grid, int row, int col, int remaining) {
  32.     // if grid is end
  33.     if (grid[row][col] == 2) {
  34.       // if only end square left, count the valid path
  35.       if (remaining == 1) {
  36.         return 1;
  37.       }
  38.      
  39.       return 0;
  40.     }
  41.    
  42.     // mark visited
  43.     int tmp = grid[row][col];
  44.     grid[row][col] = -4;
  45.    
  46.     int[][] directions = {
  47.       {-1, 0}, // up
  48.       {0, 1},  // right
  49.       {1, 0},  // down
  50.       {0, -1}  // left
  51.     };
  52.    
  53.     int countPath = 0;
  54.    
  55.     for (int i = 0; i < 4; i++) {
  56.       int[] direction = directions[i];
  57.      
  58.       int nextRow = row + direction[0];
  59.       int nextCol = col + direction[1];
  60.      
  61.       // out of bound
  62.       if (nextRow < 0 || nextRow >= ROWS || nextCol < 0 || nextCol >= COLS) {
  63.         continue;
  64.       }
  65.  
  66.       // if grid is visited (-4) or is an obstacles (-1), there is no valid path continue
  67.       if (grid[nextRow][nextCol] < 0) {
  68.         continue;
  69.       }
  70.      
  71.       countPath += backtrack(grid, nextRow, nextCol, remaining - 1);
  72.     }
  73.    
  74.     grid[row][col] = tmp;
  75.      
  76.     return countPath;
  77.   }
  78. }
RAW Paste Data