# C++ BFS solution sharing

• This problem is similar to https://leetcode.com/problems/walls-and-gates/#/description

``````class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
vector<vector<int>> ans;
int rows = matrix.size(); if (!rows) return ans;
int cols = matrix[0].size();
ans = vector<vector<int>>(rows, vector<int>(cols, INT_MAX));
queue<pair<int, int>> q; queue<int> dist;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (matrix[i][j] == 0) {
ans[i][j] = 0;
q.push({i, j});
matrix[i][j] = -1;
dist.push(0);
}
}
}

int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
while (!q.empty()) {
auto pos = q.front(); q.pop();
auto d = dist.front(); dist.pop();
for (int i = 0; i < 4; ++i) {
int xx = pos.first + dx[i], yy = pos.second + dy[i];
if (xx < 0 || yy < 0 || xx >= rows || yy >= cols) continue;
if (matrix[xx][yy] == -1) continue;
matrix[xx][yy] = -1;
dist.push(d + 1);
q.push({xx, yy});
ans[xx][yy] = std::min(ans[xx][yy], d + 1);
}
}
return ans;
}
};
``````

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