286

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        int dir[4][2] = {{1,0},{0,1},{0,-1},{-1,0}};
        queue<pair<int, int>> q;
        int rows = rooms.size(),  cols = rooms[0].size();

        // Add all gates to queue.
        for(int i=0; i<rows; i++)
            for(int j=0; j<cols; j++)
                if(rooms[i][j] == 0)
                    q.push({i, j});

        while(!q.empty()){
            auto p = q.front(); q.pop();
            int currX = p.first, currY = p.second, currDist = rooms[currX][currY];

            // Iterate in all possible directions.
            for(int i=0; i<4; i++){
                int nextX = currX + dir[i][0], nextY = currY + dir[i][1];
                if(nextX < 0 || nextX >= rows || nextY < 0 || nextY >= cols) continue;
                if(rooms[nextX][nextY] > currDist+1){
                    rooms[nextX][nextY] = currDist+1;
                    q.push({nextX, nextY});
                }
            }
        }
    }
};