First time I found my code beats 100%...


  • 0
    C

    This is the first time I find my code beats 100%. But I don't find anything special..
    Anyway, its a DP solution.

    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
            if(obstacleGrid.empty()) {
                return 0;
            }
            int row = obstacleGrid.size();
            int col = obstacleGrid[0].size();
            
            if(obstacleGrid[0][0]==1) {
                return 0;
            } else {
                obstacleGrid[0][0] = -1;
            }
            
            for(int i=1;i<col;i++) {
                if(obstacleGrid[0][i]==1){
                    obstacleGrid[0][i] = 0;
                } else {
                    obstacleGrid[0][i] = obstacleGrid[0][i-1];
                }
            }
            for(int i=1;i<row;i++) {
                if(obstacleGrid[i][0]==1){
                    obstacleGrid[i][0] = 0;
                } else {
                    obstacleGrid[i][0] = obstacleGrid[i-1][0];
                }
            }
            for(int i=1;i<row;i++) {
                for(int j=1;j<col;j++) {
                    if(obstacleGrid[i][j]==1) {
                        obstacleGrid[i][j] = 0;
                    } else {
                        obstacleGrid[i][j] = obstacleGrid[i-1][j]+obstacleGrid[i][j-1];    
                    }
                }
            }
            return -obstacleGrid[row-1][col-1];
        }
    

Log in to reply
 

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