My 4ms C++ clean-code solution


  • 0
    J
    class Solution {
        public:
            int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
                
                const int h = obstacleGrid.size();
                const int w = obstacleGrid[0].size();
                
                if (0 == h || 0 == w)
                {
                    return 0;
                }
                
                if (obstacleGrid[0][0] == 1)
                {
                    return 0;
                }
                
                if (obstacleGrid[h - 1][w - 1] == 1)
                {
                    return 0;
                }
                
                const int blockValue = -1;
                
                // update 1 to blockValue
                for (int x = 0; x < w; x++)
                {
                    for (int y = 0; y < h; y++)
                    {
                        if (obstacleGrid[y][x] == 1)
                        {
                            obstacleGrid[y][x] = blockValue;
                        }
                    }
                }
            
                // for 0, 0
                if (obstacleGrid[0][0] == 0)
                {
                    obstacleGrid[0][0] = 1;
                }
                    
                // for 1st row
                for (int x = 1; x < w; x++)
                {
                    if (obstacleGrid[0][x] == 0 && obstacleGrid[0][x - 1] == 1)
                    {
                        obstacleGrid[0][x] = 1;
                    }
                }
                
                // for 1st col
                for (int y = 1; y < h; y++)
                {
                    if (obstacleGrid[y][0] == 0 && obstacleGrid[y - 1][0] == 1)
                    {
                        obstacleGrid[y][0] = 1;
                    }
                }
                
                
                for (int y = 1; y < h; y++)
                {
                    for (int x = 1; x < w; x++)
                    {
                        const int top = obstacleGrid[y - 1][x];
                        const int left = obstacleGrid[y][x - 1];
                        
                        if (obstacleGrid[y][x] == blockValue)
                        {
                            continue;
                        }
                        
                        if (top > 0 && left > 0)
                        {
                            obstacleGrid[y][x] = top + left;
                        }
                        else
                        {
                            obstacleGrid[y][x] = std::max(std::max(top, left), 0);
                        }
                    }
                }
                
                return obstacleGrid[h - 1][w - 1];
            }
        };

Log in to reply
 

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