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 withINF.

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

两种BFS思路：

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

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

两种思路都跟寻找shortest path有关，因此容易想到用BFS。

但是第一种方法因为是从empty rooms出发，外层循环因为要遍历整个矩阵，时间复杂度就要O(m*n)，内层对每一个empty room寻找gate，用BFS实现最多需要O(m*n)时间，因此总时间复杂度就是O(m^2 * n^2)，这样是会TLE通过不了OJ的。

第二种思路从gate出发，其实是先遍历矩阵找到gate，放入queue中，之后便顺序出列，这样与每个gate距离为1的empty rooms就会进入队列（注意要更新节点的值防止重复遍历），然后距离为1的节点又对四周的empty rooms遍历，这样保证了与gate距离越远的empty rooms就会出现在queue的越后端。

关于empty rooms到gate的距离，因为在方法二中的遍历顺序确保了遍历到某个empty rooms时，一定是第一次也是最后一次遍历到，因此距离的增加是单调的，而且就是之前将该节点 (row2, col2) 加入queue的那个节点(row1, col1)的距离+1。即：

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}
        };
        Queue<Point> q = new LinkedList<Point>();
        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;
        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 });
            }
        }
    }
}

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