WallsAndGates [source code]
public class WallsAndGates {
static
/******************************************************************************/
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;
for (int i = 0; i < rooms.length; i++) {
for (int j = 0; j < rooms[0].length; j++) {
if (rooms[i][j] == 0) {
visited = new boolean[H][W];
visited[i][j] = true;
bfs(rooms, i, j, visited);
}
}
}
}
public void bfs(int[][] grid, int x, int y, boolean[][] visited) {
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] <= 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 || visited[nx][ny])
continue;
visited[nx][ny] = true;
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; }
}
}
/******************************************************************************/
public static void main(String[] args) {
WallsAndGates.Solution tester = new WallsAndGates.Solution();
int[][][] inputs = {
{
{2147483647,-1,0,2147483647,},
{2147483647,2147483647,2147483647,-1,},
{2147483647,-1,2147483647,-1,},
{0,-1,2147483647,2147483647},
},
{
{3,-1,0,1,},
{2,2,1,-1,},
{1,-1,2,-1,},
{0,-1,3,4},
}, //1
};
for (int i = 0; i < inputs.length / 2; i++) {
int[][] rooms = inputs[2 * i];
int[][] ans = inputs[1 + 2 * i];
String ansStr = Matrix.printMatrix(ans);
System.out.println(Printer.separator());
String inputStr = Matrix.printMatrix(rooms);
tester.wallsAndGates(rooms);
String outputStr = Matrix.printMatrix(rooms);
System.out.println(
Printer.wrapColor(inputStr, "magenta") +
" -> \n" + outputStr +
Printer.wrapColor(", expected: \n" + ansStr, ansStr.equals(outputStr) ? "green" : "red")
);
}
}
}
看题目的介绍的话, 大概意思好像不是很难理解, 至少人逻辑很清晰; 下面就是怎么把这个逻辑转化成一个computation, 以及, 算法;
另外这个题目的tag里面给了BFS但是没有给DFS, 或许这个是我第一次见到一个只能用BFS而不能用DFS的穷搜问题;
感觉这个题目就是一个标准的flooding问题; 搜索的时候两个思路, 是从每一个Empty开始搜索, 还是从每一个gate开始搜索? 想了一下, 我认为好像从gate开始搜索更合理一些; 另外, 如果我们是从每一个gate出发, 那么这个BFS也可以理解了: level的数量最后会直接被存储在不同的entry里面; 不过我想了一下, 其实这个问题如果真的用DFS, 好像也可以? 但是DFS的话, 会有很多的弯路, 因为DFS就算加一个depth的tag, 这个tag记录的其实是一个path的长度, 如果刚开始grid大量未填充的情况下, 这个path可能会来来回回走的很长; 事实上, 好像DFS整个就不好做: 如果你的第一个path走的很长, 甚至几乎把整个grid都填满了, 你后面其他的path怎么处理这些已经被填过的grid? 所以这个问题最终BFS才是正确的思路;
刚开始写了一个这个算法:
class Solution {
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)
flood(rooms, i, j, -2);
}
}
}
public void flood(int[][] grid, int x, int y, int distance) {
if ((x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) ||
grid[x][y] <= distance //if -1, or 0, or parent grid, or already flooded better
)
return;
if (distance < 0)
distance = 0;
else
grid[x][y] = distance;
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
if (dx == 0 && dy == 0)
continue;
flood(grid, x + dx, y + dy, distance + 1);
}
}
}
}
这个算法其实很naive, 看起来好像是BFS, 但是最后跑出来的结果是错的, 调试了一下(用打印参数的方法), 发现其实是一个DFS; 想想这个确实是是最naive的一个flooding算法, 确实是DFS的顺序;
想了一下这种简单用recursion写的算法, 基本都是DFS? 好像之前还没有碰到过用recursion写BFS的情况? 所以这里干脆就还是iteration来写这个BFS; 在思考的过程中, 发现有三个问题:
- 如果是BFS, 封装这个过程几乎是无法缺少的, 比如这里, 必须要把(x, y, distance)三个数量给封装成一起之后再推到queue里面去;
- 这个是一个矩阵结构, 不像一个tree结构天然具有一个disjoint的属性, 所以一个怎么避免重复的推queue? 事实上, 如果不避免这个重复好像也可以? 但是如果矩阵越来越大, 最后这个对速度的影响还是相当大的; 解决这个重复问题一个比较直接的思路就是用一个单独的visited matrix(array)来记录就行了;
- 在写代码的时候碰到一个问题, 这个visited flag, 什么时候设置? 之前好像有一个题目就是讨论过这个问题, 最好的方法不应该是Poll的时候设置, 而应该是push的时候设置;
- 我们的每一个BFS从一个gate出发; 如果我们在一个gate出发的BFS的过程当中, 扫到了另外一个gate, 我们怎么处理?
- 一种做法是把distance在这个地方重置, 但是如果是这种做法, 感觉就有一种同一个BFS的过程中不同的进程互相竞争的情况, 而且如果用这种方法, 也必须要不去做避免重复的处理;
- 另外一种方法就是碰到gate就直接跳过: 每一个BFS只允许有一个原点; 不过这样有一个问题, WorstCase的速度可能会很差: 你每一个gate都要重新发动一次BFS, 在WorstCase的情况下, 速度可能要有N^2 * N^2这样;
另外, 这里还有一个小问题, 就是我们这里跟flooding不完全一样, 当你在一个位置的时候, 你只能像上下左右的四个方向走, 而不是周围所有的8个邻居都可以走: 斜着走是不允许的, 这个是我一开始没有意识到的问题;
突然意识到我之前的DFS其实也就是一样的问题, 因为当时DFS做出来的错误答案跟这里8向BFS做出来的错误答案是一样的; 把DFS改成4向之后, 果然就AC了: 7ms (86%), 速度还很不错!
class Solution {
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
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)
flood(rooms, i, j, -2);
}
}
}
public void flood(int[][] grid, int x, int y, int distance) {
if ((x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) ||
grid[x][y] <= distance //if -1, or 0, or parent grid, or already flooded better
)
return;
if (distance < 0)
distance = 0;
else
grid[x][y] = distance;
for (int[] vector : directions) {
flood(grid, x + vector[0], y + vector[1], distance + 1);
}
}
}
最后这个BFS也AC了, 但是速度慢的离谱: 311(3); 感觉LeetCode对于这种数据结构的惩罚还是太严重了; 也有可能是因为这个visited的实现, 导致大量多余的array access? 感觉这些原因应该不会导致最后速度差距这么大; 很有可能最后是因为发生了我之前说的那个N^4的情况: 我让每一个0做一次原点, 最后BFS的次数太多了; 而我们的DFS是只要走一遍就行了的; 能不能改善?
想了一下, 好像没有什么特别好的方案, 如果用重启方案, 那么有一个问题无法解决, 就是怎么处理重复? 因为在一个level里面, 我们还是按顺序处理的, 这个0如果不是第一个在这个level里面被Poll出来的, 那么很有可能本来应该被这个0 populate的一个entry, 可能已经被其他的与这个0同level的entry给visit了;
要么就取消掉visited? 但是这样岂不是最后还是导致每一个entry都会发动自己的BFS? 好像不一定, 只要我们到了一个entry, 结果发现这个entry已经有更好的结果的时候, 就直接放弃就行了, 最后应该会导致一个自动多个黑洞(原点)之间划分势力范围的形式;
这个是根据上面的思路进行的一个算法: 注意, 这里还是要用到visited, 但是这个visited只记录0是否已经被visit, 因为如果我们在每一个新发现的0进行重启, 也就是重新发动一个BFS扩散, 那么这个0开始的扩散, 会重新发现之前的上家0, 最后导致一个死循环;
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; }
}
}
最后速度提升很多: 26(15), 但是跟DFS比起来好像还是不够理想, 不过已经算是可以接受的范围内了;
一个小问题, 为什么这个问题DFS也可以? 其实很正常, 关键还是看代码怎么写的; 我这里的代码规定, 只有当到达的entry有更好的结果的时候才跳过; 所以虽然最后可能path很多, 但是最后每一个entry里面保留的就是一个最小值: distance to the closest gate; 另外, 这里DFS其实也不是只走一遍就行了, 一个entry是可能被反复populate的; 比如有一个matrix, 左上角是一个gate, 右下角是一个gate, 中间全是Empty, 然后最后的情况就是, 我们先给左上角一个DFS, 这个DFS是会走遍全场的, 然后我们给右下角一个DFS, 这个DFS会抢回来右边一半的场面, 所以最后实际上完成的entry数量是1.5 * N^2;
另外这个算法的设计原型是非常类似之前学过的一个最短路径算法的, 包括这里这个类似relaxation的操作, 以及所有的distance, 最开始都是用infinity来表示;
这个是editorial1, 他们把这个叫做暴力解法:
private static final int EMPTY = Integer.MAX_VALUE;
private static final int GATE = 0;
private static final int WALL = -1;
private static final List<int[]> DIRECTIONS = Arrays.asList(
new int[] { 1, 0},
new int[] {-1, 0},
new int[] { 0, 1},
new int[] { 0, -1}
);
public void wallsAndGates(int[][] rooms) {
if (rooms.length == 0) return;
for (int row = 0; row < rooms.length; row++) {
for (int col = 0; col < rooms[0].length; col++) {
if (rooms[row][col] == EMPTY) {
rooms[row][col] = distanceToNearestGate(rooms, row, col);
}
}
}
}
private int distanceToNearestGate(int[][] rooms, int startRow, int startCol) {
int m = rooms.length;
int n = rooms[0].length;
int[][] distance = new int[m][n];
Queue<int[]> q = new LinkedList<>();
q.add(new int[] { startRow, startCol });
while (!q.isEmpty()) {
int[] point = q.poll();
int row = point[0];
int col = point[1];
for (int[] direction : DIRECTIONS) {
int r = row + direction[0];
int c = col + direction[1];
if (r < 0 || c < 0 || r >= m || c >= n || rooms[r][c] == WALL
|| distance[r][c] != 0) {
continue;
}
distance[r][c] = distance[row][col] + 1;
if (rooms[r][c] == GATE) {
return distance[r][c];
}
q.add(new int[] { r, c });
}
}
return Integer.MAX_VALUE;
}
大概看了一下, 这个算法总体的思路跟我自己的第一个BFS是类似的, 不过少许细节上处理不一样, 最后导致他这个算法超时了, 但是我的算法AC了;
- 他这里并不是当碰到一个已经被better populated的entry就退出, 而是只要碰到一个已经被anyway populated就退出;
- 他这里如果在从一个原点开始的扩散的过程中找到了另外一个0, 那么立刻这整个扩散就停止;
另外, 他这里还有一个问题, 他用这些GATE什么的东西来代替题目给的数字, 看起来很专业, 实际上反而是因为他没有看出来题目的意图, 这个题目这里其实本来就是希望你让这些特殊数值参与到运算和比较当中, 而不是把它当做一个neutral symbol;
另外, 注意他这里的distance是怎么记录的, 我的方法其实是一个attribute的思路, 他的思路则是用assoc list来完成这个attribute功能的封装, 实际上最后完成的效果是一样的;
想了一下不太理解他这里的这些变化为什么会导致最后他的算法速度比我的慢这么多? 不太想的明白, 不过回头想想, 我自己的第一个BFS其实也未必比人家快多少;
那么我的第二个BFS为什么比他快呢? 我仔细想了一下, 我还是感觉我自己的BFS1其实跟他的这个暴力解法是差不多的; 我好像看明白了, 他这里的搜索是用的我一开始就淘汰的一个思路(怪自己看他代码的时候没有看仔细): 就是从Empty开始, 找gate; 而不是从gate开始, populate; 那他这个BFS的触发点就太多了;
另外我自己的BFS2为什么比我的BFS1快? 这个其实也是很简单的: 我的BFS1, 我是碰到新的0, 就直接跳过, 所以最后每一个0会导致一个完整的N^2的扩散, 最后的复杂度也就是N^4; 但是我的BFS2, 其实不是这样的, 我的BFS2, 每一个原点最多只能扩展到他自己的势力范围的边缘: 当我们扩散到一个新的gate的时候, 这个新gate立刻开始自己的扩散, 从上家gate那里抢回来地盘, 同时抢先于上家, 抢占新的地盘(因为是recursion), 所以最后会有重复, 但是总体会有一个势力范围划分的效果;
另外, WorstCase的复杂度, editorial1和我的BFS1其实是一样的, 不过average的话, 我的比他的好很多, 因为一般来说Empty远远多于gate;
另外, 还是值得跟他这里学习的一个东西, 我用class来封装, 他直接一个array就完成了: 因为我们这里所谓的封装最后其实就是封装几个数字而已, 这个是完全不需要自己定义一个class来做的;
这个是editorial2:
private static final int EMPTY = Integer.MAX_VALUE;
private static final int GATE = 0;
private static final List<int[]> DIRECTIONS = Arrays.asList(
new int[] { 1, 0},
new int[] {-1, 0},
new int[] { 0, 1},
new int[] { 0, -1}
);
public void wallsAndGates(int[][] rooms) {
int m = rooms.length;
if (m == 0) return;
int n = rooms[0].length;
Queue<int[]> q = new LinkedList<>();
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
if (rooms[row][col] == GATE) {
q.add(new int[] { row, col });
}
}
}
while (!q.isEmpty()) {
int[] point = q.poll();
int row = point[0];
int col = point[1];
for (int[] direction : DIRECTIONS) {
int r = row + direction[0];
int c = col + direction[1];
if (r < 0 || c < 0 || r >= m || c >= n || rooms[r][c] != EMPTY) {
continue;
}
rooms[r][c] = rooms[row][col] + 1;
q.add(new int[] { r, c });
}
}
}
这个BFS的速度跟我自己的BFS2的速度是几乎差不多的(24ms), 但是我刚开始的时候很不理解, 因为这个算法看起来跟我的BFS1非常类似, 为什么最后速度这么快? 而且作者自己声称复杂度其实是N^2级别的, 刚开始也是感觉不理解, 但是后来理解了;
首先思考他这里跟我的BFS1的区别:
- 他的visited(他这里用一个distance array来自动实现)是所有的gate都共享的, 而我自己的做法, 是每一个gate的扩散独享一个自己的visited(其实我的visited最后的作用就是防止在扩散的过程中, 出现重复push的情况);
- 他这里一开始把所有的gate全都一起push进去; 这个是一个看起来不起眼, 但是非常重要的改变, 是神来之笔;
首先, 他这里也是一个基本的在BFS的过程中跳子的做法, 这个是很正常的; 但是我看的时候发现一个隐忧, 如果一个entry被之前的一个gate给populate了, 但是这个gate其实更远, 而现在的当前的这个新gate其实更近, 怎么办? 不是也被跳掉了吗? 那么这样一个relaxation的过程就没有了;
但是实际上就是因为他上面的第二条技巧, 导致这个情况永远不会发生; 当我们一开始把所有的原点全都push进去之后, 最后实际上就是所有gate轮流占地的过程; 刚开始先是每一个原点向自己周围走1个深度, 然后下一个iteration, 都占领2深度的地方: 之类有一个tie的情况, 如果在这个entry, 同时是两个原点的2深度怎么办? 无所谓, 谁先来归谁, 对最后的结果没有影响;
那么他这里的复杂度也就可以理解了, 因为他不需要实现一个利用min的relaxation的过程, 所以最后他一个entry至多只可能被visit一次, 所以最后的复杂度就是N^2; 这个算法确实是非常优秀的;
他这里还有一个巧妙的地方就是, 这个distance array的使用, 一开始全都初始化为0, 正好满足后面的计算需求;
discussion里面看到有人把这个BFS叫做Multi end BFS; 不知道这个是不是真有这么个东西;
discussion最优解, 写的有点丑, 但是背后的逻辑其实跟editorial2是类似的:
public class Solution {
public void wallsAndGates(int[][] rooms) {
if (rooms.length == 0 || rooms[0].length == 0) return;
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < rooms.length; i++) {
for (int j = 0; j < rooms[0].length; j++) {
if (rooms[i][j] == 0) queue.add(new int[]{i, j});
}
}
while (!queue.isEmpty()) {
int[] top = queue.remove();
int row = top[0], col = top[1];
if (row > 0 && rooms[row - 1][col] == Integer.MAX_VALUE) {
rooms[row - 1][col] = rooms[row][col] + 1;
queue.add(new int[]{row - 1, col});
}
if (row < rooms.length - 1 && rooms[row + 1][col] == Integer.MAX_VALUE) {
rooms[row + 1][col] = rooms[row][col] + 1;
queue.add(new int[]{row + 1, col});
}
if (col > 0 && rooms[row][col - 1] == Integer.MAX_VALUE) {
rooms[row][col - 1] = rooms[row][col] + 1;
queue.add(new int[]{row, col - 1});
}
if (col < rooms[0].length - 1 && rooms[row][col + 1] == Integer.MAX_VALUE) {
rooms[row][col + 1] = rooms[row][col] + 1;
queue.add(new int[]{row, col + 1});
}
}
}
}
discussion另外一个, 跟我的DFS解法是一样的:
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, 0);
}
private void dfs(int[][] rooms, int i, int j, int d) {
if (i < 0 || i >= rooms.length || j < 0 || j >= rooms[0].length || rooms[i][j] < d) return;
rooms[i][j] = d;
dfs(rooms, i - 1, j, d + 1);
dfs(rooms, i + 1, j, d + 1);
dfs(rooms, i, j - 1, d + 1);
dfs(rooms, i, j + 1, d + 1);
}
就是一个基于relaxation的DFS; 因为这里实际上我们只要iterate四个方向, 所以最后直接hardcode进去看起来还简洁一些;
discussion里面有人branchmark了所有的解法:
@dietpepsi said in Benchmarks of DFS and BFS:
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 StackOverflowErrorFor 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 ms320 27.790 ms 435.643 ms stackoverflow/12719.976 ms
640 85.793 ms 3502.662 msLike 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 msOnly 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 nsquare 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.
注意他的naive BFS的写法: 他的这个写法其实更符合relaxation的思想; 另外, 他这里这个直接使用child当前位置的rooms的值来判断relaxation的条件, 其实无形中也是完成了visited的功能, 还是挺好的一个写法;
他声称这个naive BFS的写法是N^3, 不过并没有给出证明;
除开这些, 基本就没有更好的解法了, 至于为什么DFS更快, 算是未解之谜了;
Problem Description
You are given a m x n 2D grid initialized with these three possible values.
-1- A wall or an obstacle.0- A gate.INF- Infinity means an empty room. We use the value 2^31 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.
For example, given the 2D grid:
INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF
After running your function, the 2D grid should be:
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4
Difficulty:Medium
Total Accepted:33.7K
Total Submissions:76.3K
Contributor: LeetCode
Companies
google facebook
Related Topics
breadth-first search
Similar Questions
Surrounded Regions Number of Islands Shortest Distance from All Buildings