floodfill
说明[font class="Apple-style-span" style="font-size: 14px; font-weight: normal;"]floodfill为C语言中的一个函数[/font]
函数名floodfill
功 能填充一个有界区域
用 法void far floodfill(int x, int y, int border);
程序例#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
10component(j) = -2
11 until num_visited = 0
12 function find_components
13 num_components = 0
14 for all nodes i
15component(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
20flood_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