286. Walls and Gates

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

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

// DFS
void helper(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;
    helper(rooms, i + 1, j, val + 1);
    helper(rooms, i - 1, j, val + 1);
    helper(rooms, i, j + 1, val + 1);
    helper(rooms, i, j - 1, val + 1);
}
void wallsAndGates(vector<vector<int>>& rooms) {
    for (int i = 0; i < rooms.size(); ++i) {
        for (int j = 0; j < rooms[0].size(); ++j) {
            if (rooms[i][j] == 0) helper(rooms, i, j, 0);
        }
    }
}

// BFS
void wallsAndGates(vector<vector<int>>& rooms) { // time: O(m * n); space: O(m * n)
    if (rooms.empty()) return;
    int m = rooms.size(), n = rooms[0].size();
    queue<pair<int, int> > q;
    vector<vector<int> > dirs({{-1, 0}, {1, 0}, {0, -1}, {0, 1}});
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (rooms[i][j] == 0)
                q.push({i, j});
        }
    }
    while (!q.empty()) {
        int i = q.front().first, j = q.front().second; q.pop();
        for (auto& dir : dirs) {
            int x = i + dir[0], y = j + dir[1];
            if (x < 0 || x >= m || y < 0 || y >= n || rooms[x][y] < rooms[i][j] + 1) continue;
            rooms[x][y] = rooms[i][j] + 1;
            q.push({x, y});
        }
    }
}