Walls and Gates

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

Tips

• 这里附上了BFS和DFS的解法，但是显然BFS更快。最先找到gate，然后以gate为root进行BFS遍历，叶子节点为四个方向。
• 最巧妙地部分是这里定义了static final d，来确定四个方向的位置，即通过用i，j +/- 1的方式来得到[i, j+1],[i+1,j],[i, j-1], [i-1, j]。
• 注意在遍历四个方向时不要出界。 *

Code:

先附上bfs，dfs在下面。

public class Solution {
    // use this d we can get the pos of the four room adjacent to x
    public static final int[] d = {0, 1, 0, -1, 0};

    public void wallsAndGates(int[][] rooms) {
        if (rooms.length == 0 || rooms[0].length == 0) {
            return;
        }
        Deque<Integer> queue = new ArrayDeque<>();
        // put the gate into the queue
        for (int i = 0; i < rooms.length; ++i) {
            for (int j = 0; j < rooms[0].length; ++j) {
                if (rooms[i][j] == 0) {
                    queue.add(i * rooms[0].length + j);
                }
            }
        }

        while (!queue.isEmpty()) {
            int x = queue.remove();
            //define the position of the gate
            //i is the row index and j is the col index
            int i = x / rooms[0].length, j = x % rooms[0].length;
            for (int k = 0; k < 4; ++k) {
                int m = i + d[k], n = j + d[k + 1];

                // keep the room inside the border and if it's empty, put the distance
                if (m >= 0 && m < rooms.length && n >= 0 && n < rooms[0].length && rooms[m][n] == Integer.MAX_VALUE) {
                    rooms[m][n] = rooms[i][j] + 1;
                    queue.add(m * rooms[0].length + n);
                }
            }
        }
    }
}

也附上dfs解法：

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);
        }
    }
}