Better view here

### The Solutions

The Multi End BFS solution used is this

```
public static final int[] d = {0, 1, 0, -1, 0};
public void wallsAndGates(int[][] rooms) {
if (rooms.length == 0) return;
int m = rooms.length, n = rooms[0].length;
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (rooms[i][j] == 0) queue.offer(i * n + j); // Put gates in the queue
while (!queue.isEmpty()) {
int x = queue.poll();
int i = x / n, j = x % n;
for (int k = 0; k < 4; ++k) {
int p = i + d[k], q = j + d[k + 1]; // empty room
if (0 <= p && p < m && 0 <= q && q < n && rooms[p][q] == Integer.MAX_VALUE) {
rooms[p][q] = rooms[i][j] + 1;
queue.offer(p * n + q);
}
}
}
}
```

The Naive BFS solution used is this

```
public static final int[] d = {0, 1, 0, -1, 0};
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);
}
private void bfs(int[][] rooms, int i, int j) {
int m = rooms.length, n = rooms[0].length;
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(i * n + j); // Put gate in the queue
while (!queue.isEmpty()) {
int x = queue.poll();
i = x / n; j = x % n;
for (int k = 0; k < 4; ++k) {
int p = i + d[k], q = j + d[k + 1];
if (0 <= p && p < m && 0 <= q && q < n && rooms[p][q] > rooms[i][j] + 1) {
rooms[p][q] = rooms[i][j] + 1;
queue.offer(p * n + q);
}
}
}
}
```

And the DFS solution used is this

```
private static int[] d = {0, 1, 0, -1, 0};
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) dfs(rooms, i, j);
}
public void dfs(int[][] rooms, int i, int j) {
for (int k = 0; k < 4; ++k) {
int p = i + d[k], q = j + d[k + 1];
if (0<= p && p < rooms.length && 0<= q && q < rooms[0].length && rooms[p][q] > rooms[i][j] + 1) {
rooms[p][q] = rooms[i][j] + 1;
dfs(rooms, p, q);
}
}
}
```

## Some benchmark:

### CASE 1: n by n matrix with all empty rooms except one gate at upper left corner.

The case generator is like this:

```
public static int[][] generateSingleGate(int n) {
int[][] rooms = new int[n][n];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
rooms[i][j] = Integer.MAX_VALUE;
rooms[0][0] = 0;
return rooms;
}
```

The results are

```
n MEBFS NaiveBFS DFS
10 0.161 ms 0.157 ms 0.715 ms
20 0.848 ms 0.482 ms 3.913 ms
40 2.672 ms 1.009 ms 25.429 ms
80 5.974 ms 3.879 ms 241.825 ms
160 9.282 ms 9.687 ms StackOverflowError
```

For this case due to the deep recursion, DFS is much slower than BFS. DFS is repeatedly updating the cell distance. Since there is only one gate in this case, NaiveBFS is expected to perform just like the MultiEndBFS.

### CASE 2: n by n matrix with a lot of gates.

The case generator is like this

```
public static int[][] generateMassiveGates(int n) {
int[][] rooms = new int[n][n];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (i % 2 != 0 || j % 2 != 0)
rooms[i][j] = Integer.MAX_VALUE;
return rooms;
}
```

The results are:

```
n MEBFS NaiveBFS DFS
10 0.244 ms 0.783 ms 0.471 ms
20 0.611 ms 3.064 ms 1.941 ms
40 1.616 ms 10.370 ms 7.248 ms
80 6.220 ms 26.910 ms 68.338 ms
160 12.291 ms 95.291 ms stackoverflow/915.517 ms
320 27.790 ms 435.643 ms stackoverflow/12719.976 ms
640 85.793 ms 3502.662 ms
```

Like expected, the DFS is much slower, and it is again overflowed.

The Naive BFS out performs DFS starting from n = 80.

If we change the vm options to -Xss20m, DFS will run in 915 ms for n=160.

Fitting the time vs n, I found that the MEBFS is O(n^2), NaiveBFS is O(n^3), DFS is O(n^4) for these cases.

### CASE 3: n by n matrix with a lot of gates but rooms are isolated by walls and gates

The case generator is this:

```
public static int[][] generateIsolateRooms(int n) {
int[][] rooms = new int[n][n];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (i % 2 != 0 && j % 2 != 0)
rooms[i][j] = Integer.MAX_VALUE;
return rooms;
}
```

The results are

```
n MEBFS NaiveBFS DFS
10 0.167 ms 0.268 ms 0.049 ms
20 0.593 ms 0.865 ms 0.196 ms
40 2.073 ms 2.096 ms 1.117 ms
80 7.347 ms 4.471 ms 2.598 ms
160 7.223 ms 4.232 ms 2.730 ms
```

Only in this case DFS wins. Since rooms are isolated, there will be limited recalculation and very shallow recursion.

The currently testcases in the OJ must somewhat in this catergory which results in a bias of DFS solutions.

### Conclusions

The performances of MultiEnd is very stable and have time complexities of O(n^2) for a `n x n`

square matrix.

The time complexity for NaiveBFS should be O(n^4) in the worst case. However is not shown in our tests.

The performance of recursive DFS is very unstable. It is much slower than BFS if the rooms are interconnected. It is only faster than BFS when small groups of rooms are isolated. In the worst case the time complexity is also O(n^4).

Thus, for this problem we should prefer BFS over DFS. And the best Solution is Multi End BFS.

And I suggest admin to add more test cases to emphasize this preference.