Concise Java Solution BFS 7ms


  • 1
    I
    public class Solution {
        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) {
                        bfs(rooms, i, j, 0);
                    }
                }
            }
        }
        
        public void bfs(int[][] rooms, int i, int j, int depth) {
            if (i < 0 || i >= rooms.length || j < 0 || j >= rooms[0].length || rooms[i][j] == -1) 
            {
                return;
            } 
                
            if (depth == 0 || depth < rooms[i][j])
            {
                rooms[i][j] = depth;
                
                bfs(rooms, i + 1, j, depth + 1);
                bfs(rooms, i, j + 1, depth + 1);
                bfs(rooms, i - 1, j, depth + 1);
                bfs(rooms, i, j - 1, depth + 1);
            }
        }
    }

  • 2

    Man, this is DFS. Nice solution though.


  • 0
    Y

    Sorry, I am confused, is this solution actually DFS, not BFS??


  • 0
    Y

    Yeah, I think so, it is DFS.


  • 0
    U

    I dont why a lot of AC posted solution using recursion named BFS....... This is a DFS.


Log in to reply
 

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