Day 27 — Unique Paths III

class Solution {
int rows = 0;
int cols = 0;
int count_zero = 0;
public int uniquePathsIII(int[][] grid) {

if(grid == null || grid.length == 0 || grid[0].length == 0)
return 0;
int[] result = new int[1];
rows = grid.length;
cols = grid[0].length;

int start_i = 0, start_j = 0;
for(int i=0; i < rows; i++){
for(int j=0; j< cols; j++){
if(grid[i][j] == 0) count_zero++;
if(grid[i][j] == 1){
start_i = i;
start_j = j;
}
}
}

dfs(grid, start_i, start_j, 0, result);
return result[0];
}

private void dfs(int[][] grid, int i, int j,
int curr, int[] result) {

if(i < 0 || i >= rows
|| j < 0 || j >= cols
|| grid[i][j] < 0) return;

if(grid[i][j] == 1 && curr > 0) return;

if( grid[i][j] == 2 ){
if(curr == count_zero)
result[0]++;
return;
}
if(grid[i][j] == 0){
grid[i][j] = -2;
curr++;
}

dfs(grid, i+1, j, curr, result );
dfs(grid, i-1, j, curr, result );
dfs(grid, i, j+1, curr, result );
dfs(grid, i, j-1, curr, result );
if(grid[i][j] == -2){
grid[i][j] = 0;
curr--;
}
return;
}
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store