floodfill c
时间: 2023-10-17 14:05:10 浏览: 36
Flood fill 是一种图像处理算法,用于填充连通区域。在计算机图形学中应用广泛。以下是C++实现:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1005;
char maze[MAXN][MAXN];
bool vis[MAXN][MAXN];
int n, m;
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; //四个方向
void dfs(int x, int y){
vis[x][y] = true;
for(int i = 0; i < 4; i++){
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if(nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && maze[nx][ny] == '.'){
dfs(nx, ny);
}
}
}
int main(){
cin >> n >> m;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> maze[i][j];
}
}
memset(vis, false, sizeof(vis));
int ans = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(!vis[i][j] && maze[i][j] == '.'){
ans++;
dfs(i, j);
}
}
}
cout << ans << endl;
return 0;
}
```
这个算法基于深度优先搜索(DFS)实现。在这个算法中,我们从起始点开始遍历,然后不断地向四个方向(上、下、左、右)扩展。
如果扩展的下一个点未被访问过,并且是可行的(在这里,我们把可以走的点标记为 '.'),我们就沿着这个点继续遍历下去。如果在扩展时发现一个点已经被访问过,我们就返回上一个点,尝试扩展其他方向。
我们使用一个二维数组 `vis` 来记录每个点是否被访问过。我们遍历整个矩阵,如果发现一个点未被访问过,并且是可行的,我们就从这个点开始进行 DFS 遍历,并且每次遍历一个连通区域时计数器加一,最后输出计数器的值就是连通区域的个数。