洪水填充
洪水填充算法（Flood Fill Algorithm）是一种用于填充图像中指定区域为同一颜色或值的算法。
洪水填充算法的基本思路是：从给定的起始点开始，将起始点所在区域填充为同一颜色或值，然后沿着边界向内扩展，填充相邻的未访问的点，直到填充完所有相邻的未访问的点。
题目 1 岛屿数量
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
35
36
37
38
int n, m;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
bool st[350][350];
void dfs(vector<vector<char>> &grid, int x, int y) {
st[x][y] = true;
for (int i = 0; i < 4; i++) {
int a = x + dx[i];
int b = y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m) {
continue;
}
if (st[a][b]) {
continue;
}
if (grid[a][b] == '0') {
continue;
}
st[a][b] = true;
dfs(grid, a, b);
}
}
int numIslands(vector<vector<char>> &grid) {
n = grid.size(), m = grid[0].size();
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '1' && !st[i][j]) {
ans++;
st[i][j] = true;
dfs(grid, i, j);
}
}
}
return ans;
}
题目 2 被围绕的区域
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
35
36
37
38
39
40
41
42
43
44
45
46
47
bool st[250][250];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
int n, m;
void dfs(int x, int y, vector<vector<char>> &board) {
st[x][y] = true;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a < 0 || b < 0 || a >= n || b >= m) {
continue;
}
if (st[a][b] || board[a][b] == 'X') {
continue;
}
st[a][b] = true;
dfs(a, b, board);
}
}
void change(vector<vector<char>> &board) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!st[i][j]) {
board[i][j] = 'X';
}
}
}
}
void solve(vector<vector<char>> &board) {
n = board.size(), m = board[0].size();
for (int i = 0; i < n; i++) {
if (board[i][0] == 'O') {
dfs(i, 0, board);
}
if (board[i][m - 1] == 'O') {
dfs(i, m - 1, board);
}
}
for (int j = 0; j < m; j++) {
if (board[0][j] == 'O') {
dfs(0, j, board);
}
if (board[n - 1][j] == 'O') {
dfs(n - 1, j, board);
}
}
change(board);
}
题目 3 最大人工岛
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// 这段代码常数时间空间不太好，仍然有改进的空间。不过AC了。
int n;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
bool st[550][550];
int id[250000];
int idx = 1;
int ans = 0;
int cnt = 0;
void dfs(int x, int y, vector<vector<int>> &grid) {
st[x][y] = true;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a < 0 || b < 0 || a >= n || b >= n) {
continue;
}
if (grid[a][b] == 0) {
continue;
}
if (st[a][b]) {
continue;
}
st[a][b] = true;
grid[a][b] = idx;
cnt++;
dfs(a, b, grid);
}
id[idx] = cnt;
ans = max(ans, cnt);
}
void check(int x, int y, vector<vector<int>> &grid) {
int temp = 0;
int cnt[4] = {0};
set<int> set1;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && b >= 0 && a < n && b < n) {
if (set1.count(grid[a][b])) {
continue;
}
set1.insert(grid[a][b]);
temp += id[grid[a][b]];
}
}
ans = max(ans, temp + 1);
}
int largestIsland(vector<vector<int>> &grid) {
ans = 0;
n = grid.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && !st[i][j]) {
grid[i][j] = idx;
cnt = 1;
dfs(i, j, grid);
idx++;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
check(i, j, grid);
}
}
}
return ans;
}
题目 4 打方块
- 炮弹位置-1
- 洪水填充天花板
- 时光倒流处理炮弹
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
vector<int> ans;
vector<vector<int>> g;
vector<vector<int>> h;
int n, m;
// 从(x, y)出发，遇到1就感染成2
// 统计新增了几个2
int dfs(int x, int y) {
if (x < 0 || y < 0 || x == n || y == m || g[x][y] != 1) {
return 0;
}
g[x][y] = 2;
return 1 + dfs(x + 1, y) + dfs(x, y + 1) + dfs(x - 1, y) +
dfs(x, y - 1);
}
bool worth(int i, int j) {
return g[i][j] == 1 &&
(i == 0 || (i > 0 && g[i - 1][j] == 2) ||
(i < n - 1 && g[i + 1][j] == 2) ||
(j > 0 && g[i][j - 1] == 2) || (j < m - 1 && g[i][j + 1] == 2));
}
vector<int> hitBricks(vector<vector<int>> &grid, vector<vector<int>> &hits) {
g = grid;
h = hits;
n = grid.size();
m = grid[0].size();
ans = vector<int>(hits.size(), 0);
if (n == 1) {
return ans;
}
for (int i = 0; i < hits.size(); i++) {
int a = hits[i][0];
int b = hits[i][1];
g[a][b]--;
}
for (int i = 0; i < m; i++) { // 对天花板洪水填充
dfs(0, i);
}
for (int i = h.size() - 1, row, col; i >= 0; i--) {
row = h[i][0];
col = h[i][1];
g[row][col]++;
if (worth(row, col)) {
ans[i] = dfs(row, col) - 1;
}
}
return ans;
}
