# 20ms Clear Java BFS solution with Brief Explanation

• The idea is for each encountered ZERO cell, do a BFS to the around empty cells. And update any empty cell's distance if smaller. Note that below code I did 2 major code refactoring to make it more concise:

1. I only add cell into queue if its cell's value needs to be
updated, alternatively, you can update in the next outer queue loop,
but queue offer and poll operations take some overheads.

2. I did not maintain a visited states (which is quite common in
BFS), because for visited cells, the cell's value must have been
updated to previous smaller COUNT, while the COUNT will increase
with BFS level.

3. Such a simple check rooms[i-1][j]>count+1 will skip -1, 0 and those visited cells!

``````public class Solution {

public void bfs(int[][] rooms, int i, int j) {
int r = rooms.length;
int c = rooms[0].length;
q.offer(i*c+j);
int count = -1;
while(!q.isEmpty()) {
count++;
int size = q.size();
while(size-->0) {
i = q.peek() / c;
j = q.peek() % c;
q.poll();
rooms[i][j] = count;
if(i>0 && rooms[i-1][j]>count+1)
q.offer((i-1)*c+j);
if(i<r-1 && rooms[i+1][j]>count+1)
q.offer((i+1)*c+j);
if(j>0 && rooms[i][j-1]>count+1)
q.offer(i*c+(j-1));
if(j<c-1 && rooms[i][j+1]>count+1)
q.offer(i*c+(j+1));
}
}
}

public void wallsAndGates(int[][] rooms) {
if(rooms.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);
}
}``````

• There is actually some inefficiency. Consider
inf inf
inf 0
your code will enqueue top left twice.

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