说明

函数名

功 能

用 法

程序例

代码实现

Flood Fill算法

说明

floodfill为C语言中的一个函数

函数名

floodfill

功 能

用指定颜色填充一个密闭区域，相当于画图中的油漆桶。

用 法

void far floodfill(int x, int y, COLORREF color);

程序例

#include <graphics.h>

#include <stdlib.h>

#include <stdio.h>

#include <conio.h>

int main(void)

{

/* request auto detection */

int gdriver = DETECT, gmode, errorcode;

int maxx, maxy;

/* initialize graphics, local variables */

initgraph(&gdriver, &gmode, "");

/* read result of initialization */

errorcode = graphresult();

if (errorcode != grOk)

/* an error occurred */

{

printf("Graphics error: %s\",

grapherrormsg(errorcode));

printf("Press any key to halt:");

getch();

exit(1);

/* terminate with an error code */

}

maxx = getmaxx();

maxy = getmaxy();

/* select drawing color */

setcolor(getmaxcolor());

/* select fill color */

setfillstyle(SOLID_FILL, getmaxcolor());

/* draw a border around the screen */

rectangle(0, 0, maxx, maxy);

/* draw some circles */

circle(maxx / 3, maxy /2, 50);

circle(maxx / 2, 20, 100);

circle(maxx-20, maxy-50, 75);

circle(20, maxy-20, 25);

/* wait for a key */

getch();

/* fill in bounded region */

floodfill(2, 2, getmaxcolor());

/* clean up */

getch();

closegraph();

return 0;

}

代码实现

#include<stdio.h>

int n,m,a[1000][1000]=,x[1000][1000]=;

int fill(int i,int j)

{ int tot=1;

if(a[j]==0||x[j]==1)

return 0;

x[j]=1;

tot+=fill(i-1,j);

tot+=fill(i+1,j);

tot+=fill(i,j-1);

tot+=fill(i,j+1);

return tot;

}

main()

{ int i,j,tot=0;

scanf("%d%d",&n,&m);

for(i=1;i<=n;i++)

for(j=1;j<=m;j++)

scanf("%d",&a[j]);

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(x[j]==0&&a[j]==1)

printf("Block %d: at (%d,%d) Size %d\",++tot,i,j,fill(i,j));

getch();

}

PASCAL实现：

s:=0;

t:=1;

queue2[1].x:=x;

queue2[1].y:=y;

f[x,y]:=true;

while s<t do

begin

inc(s);

for i:=1 to 4 do

begin

tx:=queue2[s].x+fx[i,1];

ty:=queue2[s].y+fx[i,2];

if (tx<0)or(ty<0)or(tx>n+1)or(ty>m+1)or f[tx,ty] then continue;

inc(t);

queue2[t].x:=tx;

queue2[t].y:=ty;

f[tx,ty]:=true;

end;

end;

Flood Fill算法

FloodFill是一种图论算法，对于一个图来说，可以很方便的求子图的个数。伪代码描述如下

# component(i) denotes the

# component that node i is in

1 function flood_fill(new_component)

2 do

3 num_visited = 0

4 for all nodes i

5 if component(i) = -2

6 num_visited = num_visited + 1

7 component(i) = new_component

8 for all neighbors j of node i

9 if component(j) = nil

10　component(j) = -2

11 until num_visited = 0

12 function find_components

13 num_components = 0

14 for all nodes i

15　component(node i) = nil

16 for all nodes i

17 if component(node i) is nil

18 num_components =

num_components + 1

19 component(i) = -2

20　flood_fill(component

num_components)

可以用深度优先遍历，广度优先遍历和广度优先扫描来实现，上面代码实现的是广度优先扫描

节点变化如下（没有显示即值为nil，左边是节点编号，右边是Component的值）

第一步

1 -2

第二步

1 1

4 -2

第三步

1 1

4 1

8 -2

第四步

1 1

4 1

8 1

第一次扫描结束，下面找到第一个nil的节点2，继续扫描

第五步

1 1

2 -2

4 1

8 1

第六步

1 1

2 2

4 1

7 -2

8 1

9 -2

第七步

1 1

2 2

4 1

5 -2

7 2

8 1

9 -2

第八步

1 1

2 2

4 1

5 -2

7 2

8 1

9 2

第九步

1 1

2 2

4 1

5 2

6 -2

7 2

8 1

9 2

第十步

1 1

2 2

4 1

5 2

6 2

7 2

8 1

9 2

没有-2的节点了，下面继续寻找nil节点，找到3

第11步

1 1

2 2

3 -2

4 1

5 2

6 2

7 2

8 1

9 2

第12步

1 1

2 2

3 3

4 1

5 2

6 2

7 2

8 1

9 2