Flood Fill算法是从一个区域中提取若干个连通的点与其他相邻区域区分开(或分别染成不同颜色)的经典算法。因为其思路类似洪水从一个区域扩散到所有能到达的区域而得名。

算法演示

Flood Fill算法通常用深度优先递归实现。

void flood_fill(int x,int y,int color)
{
  area[x][y]=color;
  if(x>0&&area[x-1][y]==0)flood_fill(x-1,y,color);
  if(y>0&&area[x][y-1]==0)flood_fill(x,y-1,color);
  if(x<MAX_X&&area[x+1][y]==0)flood_fill(x+1,y,color);
  if(y<MAX_Y&&area[x][y+1]==0)flood_fill(x,y+1,color);
}

例题

UVa572

#include<bits/stdc++.h>
#define MAX 105
using namespace std;

char pic[MAX][MAX]; //保存输入的图像
int m, n, idx[MAX][MAX]; //长宽与保存像素是否被搜索过

void dfs(int r, int c, int id){
    if(r < 0 || r >= m || c < 0 || c >= n)//判断退出递归
        return;
    if (idx[r][c] > 0 || pic[r][c] != '@')//如果搜索过或者不是@则退出
        return;
    idx[r][c] = id;
    for (int dr = -1; dr <= 1; dr++)//对周围一圈8个格子进行递归搜索
        for (int dc = -1; dc <= 1; dc++)
            if(dr!=0 || dc!=0)
                dfs(r + dr, c + dc, id);
}
int main(){
    while (scanf("%d %d", &m, &n)==2 && m && n)
    {
        if(m==0||n==0)
            return 0;
        for (int i = 0; i < m; i++)
            scanf("%s", pic[i]);
        memset(idx, 0, sizeof(idx));
        int cnx = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if(idx[i][j]==0 && pic[i][j] == '@')
                    dfs(i, j, ++cnx);
        printf("%d\n", cnx);
        }
    
}

一沙一世界,一花一天堂。君掌盛无边,刹那成永恒。