Description

You are given a m x n 2D 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<sup>31</sup> - 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:

image.png

After running your function, the 2D grid should be:

image.png

Solution

DFS, time O(k * m * n), space O(1)

從所有點出發(fā)太耗時了，而且會Stack Overflow，不如反過來想，從empty room（即val為0）的位置出發(fā)，做DFS填寫數(shù)組。

class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0 || rooms[0].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) {
                    dfsExpand(rooms, i, j, 0);
                }                
            }
        }
    }
    
    public void dfsExpand(int[][] rooms, int i, int j, int dis) {
        if (i < 0 || i >= rooms.length || j < 0 || j >= rooms[0].length
           || rooms[i][j] < dis) {  // rooms[i][j] is either -1 or 0
            return;
        }
        
        rooms[i][j] = dis++;
        dfsExpand(rooms, i - 1, j, dis);
        dfsExpand(rooms, i + 1, j, dis);
        dfsExpand(rooms, i, j - 1, dis);
        dfsExpand(rooms, i, j + 1, dis);
    }
}

BFS, time O(m * n), space O(m * n)

乍一看下面這個solution是有問題的，如果有多個gate，某個room的dis如何得到更新呢？但是細(xì)細(xì)想來，這個bfs算法就像是層序遍歷一樣，能夠保證按照dis由小到大地處理節(jié)點，那么這樣一來，在queue中第一次訪問到某個節(jié)點時的dis，就是這個節(jié)點的最小dis。

注意在queue offer的時候便更新dis，而非等到queue poll的時候。一是因為在添加到queue的時候就確定了dis，還有這樣做能保證每個位置最多進隊列一次。

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