286. Walls and Gates (Medium)

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

Solution: BFS

version 1: 119ms

如果当前的val比该点的值大，则不用放入queue中。

void wallsAndGates(vector<vector<int>>& rooms) {
    if (rooms.empty() || rooms[0].empty()) return;
    int m = rooms.size(), n = rooms[0].size();
    vector<int> dirs = {0,-1,0,1,0};
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (rooms[i][j] == 0) {
                queue<pair<int,int>> q; q.push({i,j});
                while (!q.empty()) {
                    int x = q.front().first, y = q.front().second, val = rooms[x][y]+1; 
                    q.pop();
                    for (int k = 0; k < 4; ++k) {
                        int x2 = x+dirs[k], y2 = y+dirs[k+1];
                        if (x2 >= 0 && x2 < m && y2 >= 0 && y2 < n && rooms[x2][y2] > val) {
                            rooms[x2][y2] = val;
                            q.push({x2,y2});
                        }
                    }

                }
            }
        }
    }
}

version 2: 102ms

先把所有的gate都放入queue中，一层层增加，避免重负搜索。

void wallsAndGates(vector<vector<int>>& rooms) {
    queue<pair<int, int>> q;
    vector<int> dirs = {0,-1,0,1,0};
    for (int i = 0; i < rooms.size(); ++i) {
        for (int j = 0; j < rooms[i].size(); ++j) {
            if (rooms[i][j] == 0) q.push({i, j});   
        }
    }
    while (!q.empty()) {
        int i = q.front().first, j = q.front().second, val = rooms[i][j]+1; q.pop();
        for (int k = 0; k < 4; ++k) {
            int x = i + dirs[k], y = j + dirs[k+1];
            if (x >= 0 && x < rooms.size() && y >= 0 && y < rooms[0].size() && rooms[x][y] > val) {
                rooms[x][y] = val;
                q.push({x, y});
            }
        }
    }
}

Solution 2: DFS 109ms

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        for (int i = 0; i < rooms.size(); ++i) {
            for (int j = 0; j < rooms[i].size(); ++j) {
                if (rooms[i][j] == 0) dfs(rooms, i, j, 0);   
            }
        }
    }

    void dfs(vector<vector<int>>& rooms, int i , int j, int val) {
        if (i < 0 || i >= rooms.size() || j < 0 || j >= rooms[0].size() || rooms[i][j] < val) return;
        rooms[i][j] = val;
        dfs(rooms, i-1, j, val+1);  
        dfs(rooms, i+1, j, val+1); 
        dfs(rooms, i, j-1, val+1); 
        dfs(rooms, i, j+1, val+1); 
    }
};