[C++] Single Template to solve all Unique path variants | DFS

I have solved all the Unique path varients with the same template, when i was solving these problems i was able to find the Best solution but there was no Brute force approach so i solved them with brute force, beacuse in interview you can not direstly go to best approach.

1.UNIQUE PATH ->Backtracking -> Memorization -> DP
2.UNIQUE PATH II ->Backtracking -> Memorization -> DP
3.UNIQUE PATH III ->Backtracking

UNIQUE PATH

Backtracking TLE

class Solution {
public:
    int count=0;
    void dfs(vector<vector<int>>& grid,int i,int j, int m,int n){
        //Base condition
        if(i<0 || j<0 || i>=grid.size() || j>=grid[0].size() || grid[i][j]==-1){
            return;
        }
        //Reached the final place increment counter
        if(i==m and j==n){
            count++;
            return;
        }
        grid[i][j]=-1;
        //Bottom
        dfs(grid,i+1,j,m,n);
        //Right
        dfs(grid,i,j+1,m,n);
        //Backtracking
        grid[i][j]=0;
    }
    int uniquePaths(int m, int n) {
        //create and initialize grid with 0
        vector<vector<int>> grid(m,vector<int>(n,0));
        dfs(grid,0,0,m-1,n-1);
        return count;
    }
};

Memorization ACCEPTED

class Solution {
public:
    int count=0;
    int dfs(vector<vector<int>>& grid,vector<vector<int>>& memo,int i,int j, int m,int n){
        //Base condition
        if(i<0 || j<0 || i>=grid.size() || j>=grid[0].size() || grid[i][j]==-1){
            return 0;
        }
        //Reached the final place increment counter
        if(i==m and j==n){
            count++;
            return 1;
        }
        if(memo[i][j]!=-1){
            return memo[i][j];
        }
        grid[i][j]=-1;
        //Bottom
        int bottom= dfs(grid,memo,i+1,j,m,n);
        //Right
        int right= dfs(grid,memo,i,j+1,m,n);
        //Backtracking
        grid[i][j]=0;
        return memo[i][j]=bottom+right;
    }
    int uniquePaths(int m, int n) {
        //create and initialize grid with 0
        vector<vector<int>> grid(m,vector<int>(n,0));
        vector<vector<int>> memo(m,vector<int>(n,-1));
        return dfs(grid,memo,0,0,m-1,n-1);
        return count;
    }
};

Dynamic programming solution: Link

UNIQUE PATH II

Backtracking TLE

class Solution {
public:
    int count=0;
    void dfs(vector<vector<int>>& obstacleGrid,int i,int j, int m,int n){
        //Base condition
        if(i<0 || j<0 || i>=obstacleGrid.size() || j>=obstacleGrid[0].size() || obstacleGrid[i][j]==-1 || obstacleGrid[i][j]==1){
            return;
        }
        //Reached the final place increment counter
        if(i==m and j==n){
            count++;
            return;
        }
        obstacleGrid[i][j]=-1;
        //Bottom
        dfs(obstacleGrid,i+1,j,m,n);
        //Right
        dfs(obstacleGrid,i,j+1,m,n);
        //Backtracking
        obstacleGrid[i][j]=0;
    }
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        dfs(obstacleGrid,0,0,obstacleGrid.size()-1,obstacleGrid[0].size()-1);
        return count;
    }
};

Memorization ACCEPTED

class Solution {
public:
    int count=0;
    int dfs(vector<vector<int>>& obstacleGrid,vector<vector<int>>& memo,int i,int j, int m,int n){
        //Base condition
        if(i<0 || j<0 || i>=obstacleGrid.size() || j>=obstacleGrid[0].size() || obstacleGrid[i][j]==-1 || obstacleGrid[i][j]==1){
            return 0;
        }
        //Reached the final place increment counter
        if(i==m and j==n){
            return 1;
        }
        if(memo[i][j]!=-1){
            return memo[i][j];
        }
        obstacleGrid[i][j]=-1;
        //Bottom
        int bottom=dfs(obstacleGrid,memo,i+1,j,m,n);
        //Right
        int right=dfs(obstacleGrid,memo,i,j+1,m,n);
        
        //Backtracking
        obstacleGrid[i][j]=0;
        return memo[i][j]=bottom+right;
    }
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        vector<vector<int>> memo(obstacleGrid.size(),vector<int>(obstacleGrid[0].size(),-1));
        return dfs(obstacleGrid,memo,0,0,obstacleGrid.size()-1,obstacleGrid[0].size()-1);
        return count;
    }
};

Dynamic programming solution: Link

UNIQUE PATH III

Backtracking ACCEPTED

class Solution {
public:
    int count=0;
    void dfs(vector<vector<int>>& grid,int i,int j, int m,int n, int empty_sq){
        //Base condition
        if(i<0 || j<0 || i>=grid.size() || j>=grid[0].size() || grid[i][j]==-1){
            return;
        }
        //Reached the final place increment counter
        if(i==m and j==n){
            if(empty_sq==0)
                count++;
            return;
        }
        grid[i][j]=-1;
        empty_sq--;
        //Bottom
        dfs(grid,i+1,j,m,n,empty_sq);
        //Top
        dfs(grid,i-1,j,m,n,empty_sq);
        //Right
        dfs(grid,i,j+1,m,n,empty_sq);
        //Left
        dfs(grid,i,j-1,m,n,empty_sq);
        //Backtracking
        grid[i][j]=0;
        empty_sq++;
    }
    int uniquePathsIII(vector<vector<int>>& grid) {
        int start_i,start_j;
        int end_i,end_j;
        int empty_sq=1;
        int row=grid.size();
        int col=grid[0].size();
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]==1){
                    start_i=i;
                    start_j=j;
                }
                if(grid[i][j]==0){
                    empty_sq++;
                }
                if(grid[i][j]==2){
                    end_i=i;
                    end_j=j;
                }
            }
        }
        dfs(grid,start_i,start_j,end_i,end_j,empty_sq);
        return count;
    }
};

Comments (1)