286. Walls and Gates

• Difficulty: Medium

• Topics: Breadth-first Search

• Similar Questions:

  • Surrounded Regions

  • Number of Islands

  • Shortest Distance from All Buildings

  • Robot Room Cleaner

  • Rotting Oranges

Problem:

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

Solutions:

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        int INF = INT_MAX;
        queue<pair<int, int>> q;
        int m = rooms.size();
        if (m == 0) return;
        int n = rooms[0].size();
        if (n == 0) return;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (rooms[i][j] == 0) {
                    q.push({i + 1, j});
                    q.push({i - 1, j});
                    q.push({i, j + 1});
                    q.push({i, j - 1});
                }
            }
        }

        int distance = 0;
        while (!q.empty()) {
            ++distance;
            int size = q.size();
            for (int k = 0; k < size; ++k) {
                int row = q.front().first;
                int col = q.front().second;
                q.pop();

                if (row < 0 || row >= m || col < 0 || col >= n || rooms[row][col] != INF)  continue;
                rooms[row][col] = distance;
                q.push({row + 1, col});
                q.push({row - 1, col});
                q.push({row, col - 1});
                q.push({row, col + 1});
            }
        }
    }
};