Java solution(beat 90.72%) very easy to understand


  • 7
    B
    public class Solution {
    private void bfs(int[][] rooms, int i, int j, int distance) {
        if (i < 0 || i >= rooms.length || j < 0 ||  j >= rooms[0].length) {
            return ;
        }
        if (rooms[i][j] < distance) {
            return ;
        } else {
            rooms[i][j] = distance;
            bfs(rooms, i + 1, j, distance + 1);
            bfs(rooms, i - 1, j, distance + 1);
            bfs(rooms, i, j + 1, distance + 1);
            bfs(rooms, i, j - 1, distance + 1);
        }
    }
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0 || rooms[0].length == 0) {
            return ;
        }
        for (int i = 0; i < rooms.length; ++i) {
            for (int j = 0; j < rooms[0].length; ++j) {
                if (rooms[i][j] == 0) {
                    bfs(rooms, i, j, 0);
                }
            }
        }
    }
    }

  • 1
    W

    I think that's not the bfs, but the dfs.


  • 0
    X

    Yes, it's dfs. BFS cannot be implemented using recursion.


  • 0
    F

    I have a question. How can DFS guarantee the "shortest" distance to any of the gates?


  • 0
    S

    @Fanchao

        if (rooms[i][j] < distance) {
            return ;
        }
    

    This will guarantee the shortest distance


  • 0
    B

    You have return; statement in if, then there is no need to use else statement for the rest part.


Log in to reply
 

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