floodfill為C語言中的一個函式。
基本介紹
- 中文名：floodfill
- 功 能：用指定顏色填充一個密閉區域
- 用 法：void far floodfill
- 程式例：#include <graphics.h>
函式名,功 能,用 法,程式例,代碼實現,Flood Fill算法,
函式名
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\n",
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>
#include<conio.h>
int n,m,a[1000][1000]={},x[1000][1000]={};
int fill(int i,int j) {
int tot=1;
if(a[i][j]==0||x[i][j]==1)
return 0;
x[i][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[i][j]);
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
if(x[i][j]==0&&a[i][j]==1)
printf("Block %d: at (%d,%d) Size %d\n",++tot,i,j,fill(i,j));
getch();
return 0;
}
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算法
# 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)
其它算法的詳細實現如下：
深搜：取一個結點，對其標記，然後標記它所有的鄰結點。對它的每一個鄰結點這么一直遞歸下去完成搜尋。
廣搜：與深搜不同的是，廣搜把結點加入佇列中。
廣度掃描（不常見）：每個結點有兩個值，一個用來記錄它屬於哪個連通子圖（c），一個用來標記是否已經訪問（v）。算法對每一個未訪問而在某個連通子圖當中的結點掃描，將其標記訪問，然後把它的鄰結點的（c）值改為當前結點的（c）值。
深搜最容易寫，但它需要一個棧。搜尋顯式圖沒問題，而對於隱式圖，棧可能就存不下了。
廣搜稍微好一點，不過也存在問題。搜尋大的圖它的佇列有可能存不下。深搜和廣搜時間複雜度均為O(N+M)。其中，N為結點數，M為邊數。
廣度掃描需要的額外空間很少，或者可以說根本不要額外空間，但是它很慢。時間複雜度是O(N^2+M)
節點變化如下（沒有顯示即值為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
