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
Problem: 980. Unique Paths III
Problem Link: leetcode.com/problems/unique-paths-iii/
Approach:
The first thing I did is counted the total cell without having obstacles. And the cell that is our source.
Now start running a DFS from that source.
In the DFS, moving 4 directionally valid cells.
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.
Once I have a valid cell, I started another DFS and reduced the total non-obstacles cell by 1.
When I reached the destination cell, I checked if I have traversed all the traversable cells.
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);
}
};