Flood fill算法是从一个区域中提取若干个连通的点与其他相邻区域区分开(或分别染成不同颜色)的经典算法。因为其思路类似洪水从一个区域扩散到所有能到达的区域而得名。在GNU Go和扫雷中,Flood Fill算法被用来计算需要被清除的区域。
算法
Flood fill算法接受三个参数:起始节点,目标颜色和替换颜色。算法-{zh-cn:遍历;zh-tw:走訪}-所有的节点以寻找和起始节点相连的节点(通过一条目标颜色的路径相连),然后
改变他们的颜色为替换颜色。目前有许多flood-fill算法的构建方式,但是他们都显示或隐式的使用队列或者堆疊}-。根据我们是否考虑当前节点对角线方向的节点,算法分为四路算法(不考虑对角线方向的节点)和八路算法(考虑对角线方向的节点)。
-{zh-cn:基于栈的递归实现方式;zh-tw:使用堆疊的遞迴實作方法}-
最简单的实现方法是采用深度优先搜索的递归方法,也可以采用广度优先搜索的迭代来实现。
/假設MAX_X與MAX_Y是圖片的寬跟高/
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
评论 (0)