Flood fill

维基百科,自由的百科全书
跳转至: 导航搜索
4个方向上的flood-fill算法示例

Flood fill算法是从一个区域中提取若干个连通的点与其他相邻区域区分开(或分别染成不同颜色)的经典算法。因为其思路类似洪水从一个区域扩散到所有能到达的区域而得名。在GNU Go扫雷中,Flood Fill算法被用来计算需要被清除的区域。

算法[编辑]

八个方向上的flood-fill递归算法

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);
 
}