A/C C++ solution, DFS, easy to understand, beat 20%


  • 0
    W

    class Solution {
    public:
    void dfs(vector<vector<int>>& rooms, int curRow, int curCol, int curDistance, int numRows, int numCols)
    {
    //cout << "curRow = " << curRow;

        if (curRow < 0 || curRow >= numRows)
            return;
    
        if (curCol <0 || curCol >= numCols)
            return;
    
        if (rooms[curRow][curCol] == -1)
            #this is a wall, don't do anything
            return;
    
        if (rooms[curRow][curCol] > (curDistance))
        {
            rooms[curRow][curCol] = curDistance;
    
    
            dfs(rooms, curRow-1, curCol, curDistance + 1, numRows, numCols);
    
    
            dfs(rooms, curRow+1, curCol, curDistance + 1, numRows, numCols);
    
    
            dfs(rooms, curRow, curCol-1, curDistance + 1, numRows, numCols);
    
            dfs(rooms, curRow, curCol+1, curDistance + 1, numRows, numCols);
        }
    
    
        else
        {
            return;
        }
    
    }
    
    void wallsAndGates(vector<vector<int>>& rooms) {
        
        int numRows = rooms.size();
        //cout << "numRows = " << numRows;
        
        if (numRows == 0)
        {
            return;
        }
        
        int numCols = rooms[0].size();
        //cout << "numCols = " << numCols;
        
        for (int rowIdx = 0; rowIdx<numRows; rowIdx++)
        {
            for (int colIdx = 0; colIdx < numCols; colIdx++)
            {
                if (rooms[rowIdx][colIdx] == 0)
                {
                    dfs(rooms, rowIdx-1,colIdx,1,  numRows, numCols);
                    dfs(rooms, rowIdx+1,colIdx,1,  numRows, numCols);
                    dfs(rooms, rowIdx,colIdx - 1,1,  numRows, numCols);      
                    dfs(rooms, rowIdx,colIdx + 1,1,  numRows, numCols);                    
                }
            }
        }
        
    
            
        
    }
    

    };


Log in to reply
 

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