C++ simple dp solution. NO extra vector. With comments


  • 0
    A

    The idea is simple. You have to transform original grid to a dp grid.
    If a cell is blocked, you have to say that there's no way to get into that cell and block the following cells depending on that cell.

    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
            bool Xhas1 = false, Yhas1 = false;
            int m = obstacleGrid.size();
            int n = obstacleGrid[0].size();
            // If first cell is blocked or vector empty, there are no paths
            if(!m || obstacleGrid[0][0] == 1) {
                return 0;
            }
            else { // There is 1 path to get to the first cell
                obstacleGrid[0][0] = 1;
            }
            // For each row
            for(int i = 1; i < m; i++){
                // If there is a blocking road before, there's no way to get to rows below
                if(Yhas1) obstacleGrid[i][0] = 0;
                // If this is blocked, you have to block the following cells and indicate there's no path here
                else if(obstacleGrid[i][0] == 1) {
                    obstacleGrid[i][0] = 0;
                    Yhas1 = true;
                }
                // There's one path to get to this cell
                else obstacleGrid[i][0] = 1;
            }
            
            // Same idea as row, but for columns
            for(int i = 1; i < n; i++){
                if(Xhas1) obstacleGrid[0][i] = 0;
                else if(obstacleGrid[0][i] == 1) {
                    obstacleGrid[0][i] = 0;
                    Xhas1 = true;
                }
                else obstacleGrid[0][i] = 1;
            }
            for(int i = 1; i < m; i++){
                for(int j = 1; j < n; j++) {
                    // If the cell is blocked, there's no way to get to the cell
                    if(obstacleGrid[i][j] == 1) obstacleGrid[i][j] = 0;
                    else {
                        // Just normal dp
                        obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
                    }
                }
            }
            return obstacleGrid[m - 1][n - 1];
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.