# Java BFS Solution

• 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.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;
}
}
}
``````

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