# C++ BFS solution O(m*n)

• Basic idea is push all 0's coordinates to the queue and set their distance[x][y] = 0 then we start BFS start from these points to update distance matrix:

``````vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> res(m,vector<int>(n,0));
if(matrix.empty()) return res;

queue<pair<int,int>> q;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(matrix[i][j] ==0) q.push(make_pair(i,j));
else                     res[i][j] = INT_MAX;
}
}
vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while(!q.empty())
{
int x= q.front().first;
int y= q.front().second;
q.pop();
for(auto dir:dirs)
{
int xx = x+dir[0];
int yy = y+dir[1];
if(inrange(xx,yy,m,n) and res[xx][yy] > res[x][y]+1)
{
res[xx][yy] = res[x][y]+1;
q.push(make_pair(xx,yy));
}
}

}
return res;
}
bool inrange(int x, int y, int m, int n)
{
if(x<0 or x>=m or y<0 or y>= n) return false;
return true;
}``````

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