词条 | floodfill |
释义 | 说明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 |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。