Java BFS Solution


  • 0
    Z

    The idea is that we start from every door and do BFS along a path. The key point here is that we don't have to go any further in the current BFS if we encounter a room that already has a shorter distance to another door.

    public class Solution {
        public void wallsAndGates(int[][] rooms) {
            if (rooms == null || rooms.length == 0 || rooms[0].length == 0) return;
            int rows = rooms.length;
            int cols = rooms[0].length;
            for (int x = 0; x < rows; ++x) {
                for (int y = 0; y < cols; ++y) {
                    if (rooms[x][y] == 0) {
                        Queue<Point> queue = new LinkedList<>();
                        queue.offer(new Point(x, y));
                        // Distance from a door to room
                        int distance = -1;
                        while (!queue.isEmpty()) {
                            int size = queue.size();
                            distance++;
                            while (size != 0) {
                                Point p = queue.poll();
                                rooms[p.x][p.y] = Math.min(rooms[p.x][p.y], distance);
                                if (isValidMove(rooms, p.x - 1, p.y, rows, cols, distance)) queue.offer(new Point(p.x - 1, p.y));
                                if (isValidMove(rooms, p.x + 1, p.y, rows, cols, distance)) queue.offer(new Point(p.x + 1, p.y));
                                if (isValidMove(rooms, p.x, p.y - 1, rows, cols, distance)) queue.offer(new Point(p.x, p.y - 1));
                                if (isValidMove(rooms, p.x, p.y + 1, rows, cols, distance)) queue.offer(new Point(p.x, p.y + 1));
                                size--;
                            }
                        }
                    }
                }
            }
        }
        
        // Helper function to test whether we can move to a new cell
        public boolean isValidMove(int[][] rooms, int x, int y, int rows, int cols, int distance) {
            if (x < 0 || x >= rows || y < 0 || y >= cols || rooms[x][y] == 0 || rooms[x][y] == -1) return false;
            // If the current distance is bigger than the previous, we don't need to go any further.
            if (rooms[x][y] <= distance + 1) return false;
            return true;
        }
        
        // Define a 2D Point class (x,y)
        class Point {
            int x;
            int y;
            Point(int row, int col) {
                x = row;
                y = col;
            }
        }
    }
    

Log in to reply
 

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