Untitled
plain_text
a month ago
1.5 kB
5
Indexable
Never
class Solution { public: vector<vector<int>> updateMatrix(vector<vector<int>>& mat) { int m = mat.size() - 1; int n = mat[0].size() - 1; vector<vector<int>> ans(m + 1, vector<int>(n + 1)); queue<pair<int, int>> bfs; for (int i = 0; i <= m; ++i) { for (int j = 0; j <= n; ++j) { if (mat[i][j] == 0) { ans[i][j] = 0; bfs.emplace(i, j); } } } while (bfs.size()) { int i = bfs.front().first; int j = bfs.front().second; bfs.pop(); if (i > 0 && mat[i -1][j]) { mat[i - 1][j] = 0; ans[i - 1][j] = ans[i][j] + 1; bfs.emplace(i - 1, j); } if (i < m && mat[i + 1][j]) { mat[i + 1][j] = 0; ans[i + 1][j] = ans[i][j] + 1; bfs.emplace(i + 1, j); } if (j > 0 && mat[i][j - 1]) { mat[i][j - 1] = 0; ans[i][j - 1] = ans[i][j] + 1; bfs.emplace(i, j - 1); } if (j < n && mat[i][j + 1]) { mat[i][j + 1] = 0; ans[i][j + 1] = ans[i][j] + 1; bfs.emplace(i, j + 1); } } return ans; } };