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);
}
My short java solution, very easy to understand


@coderatleet shouldn't the condition
rooms[i][j] < d
berooms[i][j] <= d
? When current distance is the same as new one, there's no point to continue the recursion call.


@xxj79 I have the same question. Actually, I think DFS should be slower than BFS for this problem cause you actually repeat some cells. I think the performance is unexpected because of small test cases.

dfs is costly in this case. this solution essentially for each gate traverse entire board, whereas if you do BFS, the complexity can be just O(N) by putting every gate in the queue in the beginning then traverse, it guarantees the first time hit a spot in the board is the shortest from one of the gates.

Had the same idea. This DFS uses a concept similar to relaxation in one of the shortest path algorithms introduced in CLRS, name of which I can't remember for this moment;
My code:
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); } } }
Pay a little attention to the commented line, it seems simple, but it takes care of the below situations uniformly:
 if
(x,y)
is an obstacle/wall;  if
(x,y)
is another gate;  if
(x,y)
is previously visited by this very DFS. This also prevents the DFS from going backwards.  if
(x,y)
has not been discovered by this very DFS (initiated by this very GATEA
), but it has already been discovered by a previous GATEB
who is closer to(x,y)
thantA
.
Hope this helps.
Also, I don't quite understand why DFS is faster in this problem, even faster than the O(mn) solution in the editorial article. I am pretty sure that this DFS algorithm is worse than O(mn) since there would be quite some entries that would be written more than one time.
 if