Concise, easy to understand C++ DFS solution.


  • 1
    N

    """
    class Solution {
    public:

    void dfs(vector<vector<int>>& rooms, int i, int j, int m, int n, int dist){
        if(i <0 || i>=m || j<0 || j>= n || rooms[i][j] == -1 || dist > rooms[i][j])
            return;
        rooms[i][j] = dist;
        dfs(rooms, i+1, j, m, n, dist+1);
        dfs(rooms, i-1, j, m, n, dist+1);
        dfs(rooms, i, j+1, m, n, dist+1);
        dfs(rooms, i, j-1, m, n, dist+1);
        
    }
    void wallsAndGates(vector<vector<int>>& rooms) {
        int m = rooms.size();
        if (m < 1) return;
        int n = rooms[0].size();
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                int dist = 0;
                if(rooms[i][j] == 0)
                    dfs(rooms, i, j, m, n, dist);
            }
        }
    }
    

    };
    """


  • 0
    L

    What if you update the distance of a room to the distance from a gate that is farther away?

    Shouldn't this check be made?

    if(rooms[i][j] > dist)
    
    

  • 0
    N

    @leetnessmonster Hey that check is already being made in the following line

    if(i <0 || i>=m || j<0 || j>= n || rooms[i][j] == -1 || dist > rooms[i][j])
            return;
    

Log in to reply
 

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