-
Notifications
You must be signed in to change notification settings - Fork 0
/
01Matrix.cpp
24 lines (23 loc) · 998 Bytes
/
01Matrix.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
link-> https://leetcode.com/problems/01-matrix/submissions/870536274/?envType=study-plan&id=algorithm-i
class Solution {
public:
vector<int> DIR = {0, 1, 0, -1, 0}; // up,down,left ,right
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
queue<pair<int, int>> q;
for (int r = 0; r < m; ++r)
for (int c = 0; c < n; ++c)
if (mat[r][c] == 0) q.emplace(r, c);//emplace()->inserts the key and its element in the map container
else mat[r][c] = -1; // Marked as not processed yet!
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int i = 0; i < 4; ++i) {
int nr = r + DIR[i], nc = c + DIR[i+1];
if (nr < 0 || nr == m || nc < 0 || nc == n || mat[nr][nc] != -1) continue;
mat[nr][nc] = mat[r][c] + 1;
q.emplace(nr, nc);
}
}
return mat;
}
};