My short java solution, very easy to understand


  • 101
    H
    public void wallsAndGates(int[][] rooms) {
        for (int i = 0; i < rooms.length; i++)
            for (int j = 0; j < rooms[0].length; j++)
                if (rooms[i][j] == 0) dfs(rooms, i, j, 0);
    }
    
    private void dfs(int[][] rooms, int i, int j, int d) {
        if (i < 0 || i >= rooms.length || j < 0 || j >= rooms[0].length || rooms[i][j] < d) return;
        rooms[i][j] = d;
        dfs(rooms, i - 1, j, d + 1);
        dfs(rooms, i + 1, j, d + 1);
        dfs(rooms, i, j - 1, d + 1);
        dfs(rooms, i, j + 1, d + 1);
    }

  • 0
    Y

    Nice solution. Thanks for sharing!


  • 0
    H

    Thanks! :) :) :)


  • 0
    I

    What is the time complexity? is it O(mn)?


  • 1
    T

    Wow, elegant and easy to understand. Thank you so much.


  • 4
    B

    I think it should be O(kmn) where k is the number of 0.


  • 5
    J

    I am wondering how the algorithm makes sure the result is the shortest distance for every room?


  • -1
    S

    I think time complexity should be O(mn) since each entry will be visited at most 4 times which means O(4mn)


  • 0
    D

    This is dfs right?


  • 6
    C

    @jccg1000021953

    rooms[i][j]<d in the base condition makes sure distance for room is not updated when it (one passed in recursive call) is more than the existing distance. It also serves as a stopping condition when met with obstacles, since -1 will always be less than any distance.


  • 0
    R

    Great solution! Thank you very much!


  • 0
    D

    This method is so good.


  • 0
    L

    How do you measure the time complexity of DFS. I got the O(mn) part, but how do you measure the complexity of recursive calls?


  • 0
    Z
    This post is deleted!

  • 0

    @coderatleet shouldn't the condition rooms[i][j] < d be rooms[i][j] <= d? When current distance is the same as new one, there's no point to continue the recursion call.


  • 2
    A

    @daydayup That would stop the initial case where gate [i][j] = 0


  • 1
    X

    Why dfs runs much faster than bfs for this problem?? Anybody knows? To me neither of them have repeated calls and should have similar performance in speed.


  • 0
    F

    @xxj79 I have the same question. Actually, I think DFS should be slower than BFS for this problem cause you actually repeat some cells. I think the performance is unexpected because of small test cases.


  • 0
    X

    dfs is costly in this case. this solution essentially for each gate traverse entire board, whereas if you do BFS, the complexity can be just O(N) by putting every gate in the queue in the beginning then traverse, it guarantees the first time hit a spot in the board is the shortest from one of the gates.


  • 0

    Had the same idea. This DFS uses a concept similar to relaxation in one of the shortest path algorithms introduced in CLRS, name of which I can't remember for this moment;

    My code:

    class Solution {
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        public void wallsAndGates(int[][] rooms) {
            for (int i = 0; i < rooms.length; i++) {
                for (int j = 0; j < rooms[0].length; j++) {
                    if (rooms[i][j] == 0)
                        flood(rooms, i, j, -2);
                }
            }
        }
    
        public void flood(int[][] grid, int x, int y, int distance) {
            if ((x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) ||
                grid[x][y] <= distance    //if -1, or 0, or parent grid, or already flooded better
                )
                return;
            if (distance < 0)
                distance = 0;
            else
                grid[x][y] = distance;
            for (int[] vector : directions) {
                flood(grid, x + vector[0], y + vector[1], distance + 1);
            }
        }
    }
    

    Pay a little attention to the commented line, it seems simple, but it takes care of the below situations uniformly:

    • if (x,y) is an obstacle/wall;
    • if (x,y) is another gate;
    • if (x,y) is previously visited by this very DFS. This also prevents the DFS from going backwards.
    • if (x,y) has not been discovered by this very DFS (initiated by this very GATE A), but it has already been discovered by a previous GATE B who is closer to (x,y) thant A.

    Hope this helps.

    Also, I don't quite understand why DFS is faster in this problem, even faster than the O(mn) solution in the editorial article. I am pretty sure that this DFS algorithm is worse than O(mn) since there would be quite some entries that would be written more than one time.


Log in to reply
 

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