一、思路

Flood fill算法接受三个参数：起始节点，目标颜色和替换颜色。算法遍历所有的节点以寻找和起始节点相连的节点（通过一条目标颜色的路径相连），然后 改变他们的颜色为替换颜色。目前有许多flood-fill算法的构建方式，但是他们都显示或隐式的使用队列或者栈 根据我们是否考虑当前节点对角线方向的节点，算法分为四路算法（不考虑对角线方向的节点）和八路算法（考虑对角线方向的节点）。

最简单的实现方法是采用深度优先搜索的递归方法，也可以采用广度优先搜索的迭代来实现。

二、代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

//将递归算法转化为一般的非递归算法，一般都可以通过Stack（栈）来实现，以递归的注入填充算法为例:

//（1）递归注入填充算法：

void FloodSeedFill(CDC* pDC, int x, int y, COLORREF colorOld, COLORREF colorNew)
{
	if (pDC->GetPixel( CPoint(x, y) ) == colorOld)
	{
		pDC->SetPixel( CPoint(x, y), colorNew);

		FloodSeedFill(pDC, x, y - 1, colorOld, colorNew); // 上
		FloodSeedFill(pDC, x + 1, y, colorOld, colorNew); // 右
		FloodSeedFill(pDC, x, y + 1, colorOld, colorNew); // 下
		FloodSeedFill(pDC, x - 1, y, colorOld, colorNew); // 左
	}
}

//（2）非递归注入填充算法（C++ STL Stack）：

void FloodSeedFill(CDC* pDC, int x, int y, COLORREF colorOld, COLORREF colorNew)
{
	stack <CPoint> ptStack; //用来保存需要填充的点

	CPoint ptCurrent = CPoint(x, y);	//将种子点设为当前需要填的点
	ptStack.push( ptCurrent );			//将种子点压入堆栈中
	
	while ( !ptStack.empty() )
	{
		ptCurrent = ptStack.top();
		pDC->SetPixel( ptCurrent, colorNew ); // 填充该点
		ptStack.pop();	// 出栈

		CPoint ptArround[ 4 ];
		ptArround[ 0 ] = CPoint( ptCurrent.x - 1, ptCurrent.y );
		ptArround[ 1 ] = CPoint( ptCurrent.x + 1, ptCurrent.y );
		ptArround[ 2 ] = CPoint( ptCurrent.x, ptCurrent.y - 1 );
		ptArround[ 3 ] = CPoint( ptCurrent.x, ptCurrent.y + 1 );
		
		// 将当前点点周围四个点压入栈中
		for ( int i = 0; i < 4; i ++ )
		{
			if( pDC->GetPixel( ptArround[ i ] ) == colorOld )
			{
				ptStack.push( ptArround[ i ] );  // 入栈
			}
		}
	}
}