# 144ms C++ solution with BFS

• ``````class Solution {
public:
void wallsAndGates(vector<vector<int>>& rooms) {

queue<pair<int,int>> q;

int rows = rooms.size();
if (rows == 0)
return;
int cols = rooms[0].size();

// Add the (i,j) coordinate of every gate to the queue
for (int i=0; i<rows; ++i) {
for (int j=0; j<cols; ++j) {
pair<int, int> p(i, j);
if (rooms[i][j]==0) {
q.push(p);
}
}
}
array<int, 5> dir = {0, 1, 0, -1, 0};

// Breadth first search
while (!q.empty()) {
pair<int,int> p = q.front();
q.pop();

// For every element in the queue, try to move in all four directions (east, north, west, south)
for (int k=0; k<4; ++k) {
// Coordinates of the old position
int old_i = p.first;
int old_j = p.second;

// Coordinates of the new position
int new_i = old_i+dir[k];
int new_j = old_j+dir[k+1];

/** If the new position is still within the boundaries of rooms (the first four conditions of the if statement),
and if the new position corresponds to an empty room (rooms[new_i][new_j]==INT_MAX),
then update rooms[new_i][new_j] to be rooms[old_i][old_j]+1
(= distance of the old position to the nearest gate + 1).
Then add the coordinates of the new position to the queue.
*/
if (new_i>=0 && new_i<rows && new_j>=0 && new_j<cols && rooms[new_i][new_j]==INT_MAX) {
rooms[new_i][new_j] = rooms[old_i][old_j]+1;
pair<int,int> p2(new_i, new_j);
q.push(p2);
}
}

}
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.