洪水填充算法（flood fill algorithm），也称为泛洪算法，用于将格点的某一个连通区域内的所有格点状态修改为目标状态，状态往往用颜色表示。一般的处理方法是，从一个起始点开始把附近与其连通的点填充成新的颜色，直到连通区域内的所有点都被处理过为止，因为其思路类似洪水从一个区域扩散到所有能到达的其他区域而得名。
DFS、BFS 都可以用来实现洪水填充算法，常见的邻域包括四邻域和八邻域等。
#include <cstdio>
char f[105][105];
int n, m;
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
void dfs(int x, int y) {
f[x][y] = '.';
for (int i = 0; i < 8; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx >= 0 && xx < n && yy >= 0 && yy < m && f[xx][yy] == 'W') {
dfs(xx, yy);
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) scanf("%s", f[i]);
int lake = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (f[i][j] == 'W') {
lake++;
dfs(i, j);
}
printf("%d\n", lake);
return 0;
}
#include <cstdio>
#include <queue>
using namespace std;
char f[105][105];
int n, m;
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
struct Node {
int x, y;
};
void bfs(int x, int y) {
f[x][y] = '.';
queue<Node> q;
q.push({x, y});
while (!q.empty()) {
Node t = q.front(); q.pop();
for (int i = 0; i < 8; i++) {
int xx = t.x + dx[i], yy = t.y + dy[i];
if (xx >= 0 && xx < n && yy >= 0 && yy < m && f[xx][yy] == 'W') {
f[xx][yy] = '.';
q.push({xx, yy});
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) scanf("%s", f[i]);
int lake = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (f[i][j] == 'W') {
lake++;
bfs(i, j);
}
printf("%d\n", lake);
return 0;
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。