-
floodfill
鎖定
floodfill為C語言中的一個函數。
- 中文名
- floodfill
- 功 能
- 用指定顏色填充一個密閉區域
- 用 法
- void far floodfill
floodfill函數名
floodfill
floodfill功 能
用指定顏色填充一個密閉區域,相當於畫圖中的油漆桶。
floodfill用 法
void far floodfill(int x, int y, COLORREF color);
floodfill程序例
#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; }
floodfill代碼實現
#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;
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)
可以用深度優先遍歷,廣度優先遍歷和廣度優先掃描(速度很慢)來實現,上面代碼實現的是廣度優先掃描
深搜:取一個結點,對其標記,然後標記它所有的鄰結點。對它的每一個鄰結點這麼一直遞歸下去完成搜索。
廣搜:與深搜不同的是,廣搜把結點加入隊列中。
廣度掃描(不常見):每個結點有兩個值,一個用來記錄它屬於哪個連通子圖(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
- 參考資料
-
- 1. floodfill .nocow[引用日期2014-01-15]
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:21次歷史版本
- 最近更新: canguanxihu