# Walls and Gates

You are given am x n2D grid initialized with these three possible values.

1. `-1`- A wall or an obstacle.

2. `0`- A gate.

3. `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 itsnearestgate. If it is impossible to reach a gate, it should be filled with`INF`.

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``````

## Analysis

1. 从empty room出发，寻找找gate；

2. 从gate出发，寻找empty room。

``rooms[row2][col2] = rooms[row1][col1] + 1``

DFS的解法在于从gate出发进行dfs搜索，但是DFS的问题在于可能会多次搜索到统一位置，并且如果比当前存的距离短，则更新当前的距离，因此算法不够高效稳定。

## Solution

BFS - starting from GATE - (23 ms, faster than 18.59%)

``````class Solution {
public void wallsAndGates(int[][] rooms) {
if (rooms == null || rooms.length == 0 || rooms[0].length == 0) {
return;
}
int EMPTY = Integer.MAX_VALUE;
int GATE = 0;
int WALL = -1;

int[][] direction = new int[][] {
{-1, 0},
{0, -1},
{1, 0},
{0, 1}
};
int m = rooms.length;
int n = rooms[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (rooms[i][j] == GATE) {
q.offer(new Point(i, j));
}

}
}

while (!q.isEmpty()) {
Point p = q.poll();

for (int k = 0; k < direction.length; k++) {
int row = p.row + direction[k][0];
int col = p.col + direction[k][1];
if (row < 0 || row > m - 1 || col < 0 || col > n - 1 || rooms[row][col] != EMPTY) {
continue;
}
rooms[row][col] = rooms[p.row][p.col] + 1;
q.offer(new Point(row, col));
}

}

}
class Point {
int row;
int col;
Point(int row, int col) {
this.row = row;
this.col = col;
}
}
}``````

LeetCode Official Solution (23 ms, faster than 18.59%)

``````class Solution {
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;
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 });
}
}
}
}``````

## Reference

LeetCode Solution: https://leetcode.com/problems/walls-and-gates/solution/

Benchmarks of DFS and BFS

https://leetcode.com/problems/walls-and-gates/discuss/72748/Benchmarks-of-DFS-and-BFS

Last updated