hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Unique Paths III


  • Approach:

    1. The first thing I did is counted the total cell without having obstacles. And the cell that is our source.

    2. Now start running a DFS from that source.

    3. In the DFS, moving 4 directionally valid cells.

    4. A cell is valid if the coordinate does not go outside of the grid if the cell is not already visited (as in a path we can traverse a cell only once) if the cell can be traversed.

    5. Once I have a valid cell, I started another DFS and reduced the total non-obstacles cell by 1.

    6. When I reached the destination cell, I checked if I have traversed all the traversable cells.

    7. If I did then increase the result by 1.


  • Time and Space Complexity:

      • Time Complexity: O(4^(M*N))

      • Space Complexity: O(M*N)


Code [C++]

class Solution {

public:


int dx[4] = {0, 0, 1, -1};

int dy[4] = {1, -1, 0, 0};


int pathFind(vector<vector<int>> & grid, vector<vector<bool>>&visited, int x, int y, int m, int n, int nobs){

if(grid[x][y] == 2){

return (nobs == -1);

}

int ret = 0;

for(int i=0; i<4; i++){

int adj_x = x + dx[i];

int adj_y = y + dy[i];

if(adj_x < 0 || adj_x >= m || adj_y < 0 || adj_y>= n) continue;

if(grid[adj_x][adj_y] == -1 || visited[adj_x][adj_y]) continue;

visited[adj_x][adj_y] = true;

ret += pathFind(grid, visited, adj_x, adj_y, m, n, nobs-1);

visited[adj_x][adj_y] = false;

}

return ret;

}


int uniquePathsIII(vector<vector<int>>& grid) {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int m = grid.size();

int n = grid[0].size();

vector<vector<bool>>visited(m+1, vector<bool>(n+1, false));

int srcx, srcy;

int nobs = 0;

for(int i=0; i<m; i++){

for(int j=0; j<n; j++){

if(grid[i][j] == 1){

srcx = i, srcy= j;

}

if(grid[i][j] == 0) nobs++;

}

}

// cout<<nobs<<endl;

visited[srcx][srcy] = true;

return pathFind(grid, visited, srcx, srcy, m, n, nobs);

}

};