Queue and BFS

Strongly Connected Component

Flood Fill

Hints: use visited label

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
if (image[sr][sc] == newColor) return image;
int oldColor = image[sr][sc];
int m = image.size();
int n = image[0].size();

auto map = image;
vector<pair<int, int>> dirs = {
{1, 0}, {0, 1}, {-1, 0}, {0, -1}
};
stack<pair<int, int>> S;
S.push({sr, sc});
while (!S.empty()) {
auto p = S.top(); S.pop();
map[p.first][p.second] = newColor;
for (auto dir : dirs) {
int i = dir.first + p.first;
int j = dir.second + p.second;

if (i < 0 || i == m || j < 0 || j == n || map[i][j] != oldColor) continue;
S.push({i, j});
}
}

return map;
}

Distance to Nearest 0 in Matrix

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<pair<int, int>> dirs = {
{1, 0}, {0, 1}, {-1, 0}, {0, -1}
};

vector<vector<int>> map(m, vector<int>(n, -1));
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({i, j});
map[i][j] = 0;
}
}
}

// BFS
while (!Q.empty()) {
auto p = Q.front(); Q.pop();
for (auto dir : dirs) {
int i = p.first + dir.first;
int j = p.second + dir.second;
if (i < 0 || i == m || j < 0 || j == n) continue;
if (map[i][j] == -1) {
map[i][j] = map[p.first][p.second] + 1;
Q.push({i, j});
}
}
}

return map;
}