2021年 1月16日
FloodFill 洪水灌溉算法 O(M * N)
#include <iostream>
#include <vector>
using namespace std;
void dfs(vector<vector<int>>& grid, int m, int n, int x, int y, vector<vector<int>>& visited) {
if (x < 0 || y < 0 || x == n || y == m || visited[y][x] || !grid[y][x])
return;
visited[y][x] = 1;
dfs(grid, m, n, x - 1, y, visited);
dfs(grid, m, n, x + 1, y, visited);
dfs(grid, m, n, x, y - 1, visited);
dfs(grid, m, n, x, y + 1, visited);
}
int floodFill(vector<vector<int>>& grid, int m, int n) {
vector<vector<int>> visited(m, vector<int>(n));
int num = 0;
for (int y = 0; y < m; ++y)
for (int x = 0; x < n; ++x)
if (grid[y][x] && !visited[y][x]) {
dfs(grid, m, n, x, y, visited);
++num;
}
return num;
}
int main() {
int t, index = 1;
cin >> t;
while (t--) {
cout << "Case #" + to_string(index++) + ":" << endl;
int r, c;
cin >> r >> c;
vector<vector<int>> grid(r, vector<int>(c));
string row;
for (int y = 0; y < r; ++y) {
cin >> row;
for (int x = 0; x < c; ++x) grid[y][x] = row[x] - '0';
}
int n;
cin >> n;
while (n--) {
char op;
cin >> op;
switch (op) {
case 'M':
int x, y, z;
cin >> x >> y >> z;
grid[x][y] = z;
break;
case 'Q':
cout << floodFill(grid, r, c) << endl;
break;
}
}
}
return 0;
}