Hi, I have this other BFS, and according to OJ, this one is actually almost as fast as the multi-end BFS, the code I used is the second approach in the editorial article.

Instead of starting a brand new BFS from each gate from ground up, when I meet a different gate during the BFS starting from one gate, I recurse on this new gate, to start a new BFS. The previous BFS is paused of cause. The new BFS will likely reclaim some entries from the previous BFS, but the overlapping should not be too much. And when this new BFS returns, much more entries will be ignored by the previous BFS;

I am not able to precisely quantify the speed of this algorithm, since it suffers the kind of fluctuation as the DFS, but I am just posting it here for reference.

Note that visited only cares about all gates: I have to do this to prevent the gate A discover gate B then B discovers A again ending up in a dead loop.

class Solution {
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public void wallsAndGates(int[][] rooms) {
if (rooms.length <= 0 || rooms == null)
return;
int H = rooms.length, W = rooms[0].length;
boolean[][] visited = new boolean[H][W];
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, visited);
}
}
}
}
public void bfs(int[][] grid, int x, int y, boolean[][] visited) {
visited[x][y] = true;
Queue<Entry> q = new LinkedList<>();
q.offer(new Entry(x, y, -2));
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
Entry e = q.poll();
int ex = e.x, ey = e.y, d = e.distance;
if (grid[ex][ey] == 0 && !visited[ex][ey]) { //restart when encounter a new 0;
bfs(grid, ex, ey, visited);
}
if (grid[ex][ey] <= d) //if -1, or 0, or already populated by a closer 0;
continue;
if (d < 0)
d = 0;
else
grid[ex][ey] = d;
for (int[] vector : directions) {
int nx = ex + vector[0], ny = ey + vector[1];
if (nx < 0 || ny < 0 || nx >= grid.length || ny >= grid[0].length)
continue;
q.offer(new Entry(nx, ny, d + 1));
}
}
}
}
private static class Entry {
int x, y, distance;
public Entry(int x, int y, int distance) { this.x = x; this.y = y; this.distance = distance; }
}
}