# C++ BFS solution based on queue

• In each turn, set all '1's we can reach to negative, which could be seen as "visited".

class Solution {
public:

vector<int> dir = {0,1,0,-1,0};

vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
// 1. initialize
int m = matrix.size(), n = m ? matrix[0].size() : 0, steps = 1;
queue<pair<int,int>> que;
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j)
if(matrix[i][j] == 0) que.push({i,j});
}

// 2. BFS
while(!que.empty()){
int sz = que.size();
while(sz-->0){
auto p = que.front();
que.pop();
for(int d = 0; d <4 ; ++d){
int x = p.first + dir[d], y = p.second + dir[d+1];
if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= 0) continue;
matrix[x][y] = -steps;
que.push({x,y});
}
}
steps++;
}

// 3. reset values
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j)
if(matrix[i][j] < 0) matrix[i][j] = -matrix[i][j];
}
return matrix;
}
};

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