floodfill演算法

A. 填充演算法的注入填充區域演算法

注入填充演算法(FloodFill Algorithm)用於內部定義區域，以改變整個區域的顏色屬性，它把區域內的原像素點值改變成另一種像素點值。演算法3.2用於填充八連通的內部定義區域。演算法中，read ¡ pixel(x; y)表示讀出像素點(x; y)像素點值。old-value為像素點的原值, new-value為將要填充的新值。
[演算法3.2] 注入填充區域演算法。
Procere flood-fill-8(x,y,old-value,new-value)
BEGIN
IF read-pixel(x,y)=old-value THEN
BEGIN
write-pixel(x,y,new-value)
flood-fill-8(x,y-1,old-value,new-value)
flood-fill-8(x,y+1,old-value,new-value)
flood-fill-8(x-1,y,old-value,new-value)
flood-fill-8(x+1,y,old-value,new-value)
flood-fill-8(x+1,y-1,old-value,new-value)
flood-fill-8(x+1,y+1,old-value,new-value)
flood-fill-8(x-1,y-1,old-value,new-value)
flood-fill-8(x-1,y+1,old-value,new-value)
END
ENDIF
END
此演算法所採用的基本方法是首先確定(x; y)點的像素點是否在區域內尚未被訪問過的那一部分之中，也就是說，如果這個像素點的值是原始值old-value，則需要把它改為填充的值new-value，然後按八連通區域性質先後訪問其八個相鄰的像素點，當訪問其中每一個近鄰像素點時，都要進行遞歸調用。此演算法通過在四個方向而不是八個方向上擴展，就可以用來填充一個內部定義的四連通式區域。這時程序只要有前面四個flood-fill-8(...)語句就可以了.

B. 極高分求 noip 常用演算法 c++源碼

什麼？是C++……無奈，我手頭的程序都是PASCAL的……

1、初等演算法
2、高精度的四則運算
3、查找演算法（順序查找、二分法、哈希查找等等）
這三個較簡單，在網路上搜索即可

4、排序演算法
其實只需要背快排、堆排即可，其他的速度比較慢不推薦

5、分枝限界法
網路搜索

6、圖的演算法
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;
}

7、其他：
KMP:
#include<iostream>
#include<time.h>
#include<string>
using namespace std;
void init(string ,string);
void show(char [],int);
int kmp(string ,string,int pos);
void get_next(char*,int *);
string s1,t1;
int m,n;
char *s;
char *t;
int *next;
/*************************MAIN**************************************/
int main(int argc[],char*args[])
{

double t=clock();
cout<<"找到位置為："<<kmp("acbsabcaacabaabaabcacaabc","abaabca",1)<<endl;
delete[] s;
delete[] next;
cout<<"耗時："<<(clock()-t)/1000<<"毫秒！"<<endl;
return 0;
}
/**********************++++NEXT++++********************************/
void get_next(char s[],int ne[])
{
ne =new int[n+1];
next=new int[n+1];
ne[0]=9999;
int i(1),j(0);
ne[1]=0;
while(i<=(int)(t[0]))//數組是字元型的，要轉化為整數
{
if(j==0||t[i]==t[j]){++i;++j;ne[i]=j;}
else j=ne[j];
}
for( i=1;i<=n;i++)
{
cout<<"next["<<i<<"]="<<ne[i]<<endl;
next[i]=ne[i];
}
}
/********************++++KMP+++**********************************/
int kmp(string s0,string t0,int pos)
{
init(s0,t0);
int i=pos,j=1;
while(i<=((int)(s[0]))&&(j<=((int)(t[0]))))
{
if((j==0)||(s[i]==t[j])){++i;++j;}
else j=next[j];

}
if(j>(int)(t[0])) return i-((int)(t[0]));
else return 0;

}
/**********************************************************/
void init(string ss,string tt)
{ s1=ss;
t1=tt;
m=s1.length();
n=t1.length();
//if((s=(char*)malloc((m+1)*sizeof(char)))<0){cout<<"failed\n";return;}
s=new char[m+1];
s[0]=m;
//if((t=(char*) malloc((n+1)*sizeof(char)))<0) {cout<<"failed\n";return;}
t=new char[n+1];
t[0]=n;
for(int i=1;i<=m;i++)
s[i]=s1.at(i-1);
for( i=1;i<=n;i++)
t[i]=t1.at(i-1);
cout<<"原字元串"; show(s,m);
cout<<"模式字元串： "; show(t,n);
get_next(t,next);
}
/*******************++++SHOW+++**************************************/
void show(char s[],int n )
{
for(int i=1;i<=n;i++)
cout<<s[i]<<" ";
cout<<endl;
cout<<"length： "<<int(s[0])<<"\n";
}

prim:
#include <stdio.h>
#define INFINITY 32767
#define MAX 4
typedef struct{
int vexnum;
int arcs[MAX][MAX];
}Graph;//圖的結構體
//*****************創建圖的鄰接矩陣 *****************
void Creat_Graph(Graph *g)
{
int i,j,v1,v2,w,num;
printf("please input vertex number:\n");
scanf("%d",&num);
g->vexnum=num;
for(i=0;i<num;i++)
for(j=0;j<num;j++)
if(i==j)
g->arcs[i][j]=0; //無環，對角線為0
else
g->arcs[i][j]=INFINITY;
printf("please input vertex ,vertex ,weight :(end with -1,-1)\n");
do
{ printf("<vertex1,vertex2,weight>:");
scanf("%d,%d,%d",&v1,&v2,&w);
if(v1>=0&&v1<num&&v2>=0&&v2<num)
{
g->arcs[v1][v2]=w;
g->arcs[v2][v1]=w;
}
}while(!(v1==-1&&v2==-1));//循環的條件
}

Kruskal:
#include<iostream>
#include<vector>
#include<algorithm>
#define max 100

using namespace std;

struct Edge{
int vi,vj,w;
};

bool lequal(Edge const* t1, Edge const* t2){
return (t1->w<t2->w);
}

int V,E;
vector <Edge*>edges;
vector <Edge*>mst;
int cicles[max];

int main(){

int i,W,number,c;
Edge *e;

c=1;
while(true){
edges.clear();
mst.clear();
cin>>V>>E;
if(!V && !E) break;

for(i=0;i<E;i++){
e = new Edge;
cin>>e->vi>>e->vj>>e->w;
edges.push_back(e);
}

sort(edges.begin(),edges.end(),lequal);
for(i=0;i<V;i++) cicles[i] = i;

while(mst.size()<(V-1) && edges.size()){
if(cicles[edges[0]->vi]!=cicles[edges[0]->vj]){
number = cicles[edges[0]->vj];
for(i=0;i<V;i++) {
if(cicles[i]==number)
cicles[i] = cicles[edges[0]->vi];
}
mst.push_back(edges[0]);
}
edges.erase(edges.begin(),edges.begin()+1);
}
W = 0;
for(i=0;i<mst.size();i++) {
W+=mst[i]->w;
}
cout<<"Case "<<c++<<":"<<endl;
cout<<"The Minimun Spanning Tree has cost: "<<W<<endl;
}

return 0;
}

floyd:
program floyd;
var st,en,f:integer;
n,i,j,x:integer;
a:array[1..10,1..10]of integer;
path,map1,map2:array[1..10,1..10]of integer;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(a[i,j]);
path[i,j]:=j;
end;
readln;
end;
for x:=1 to n do
for i:=1 to n do
for j:=1 to n do
if a[i,j]>a[i,x]+a[x,j] then
begin
a[i,j]:=a[i,x]+a[x,j];
path[i,j]:=path[i,x];
end;
readln(st,en);
writeln(a[st,en]);
writeln;
f:=st;
while f<> en do
begin
write(f);
write('=>');
f:=path[f,en];
end;
write(en);
end.
完畢

C. 求八向聯通的種子填充演算法代碼，用C/C++

bool pop(int &x, int &y)
{
if(stackPointer > 0)
{
int p = stack[stackPointer];
x = p / h;
y = p % h;
stackPointer--;
return 1;
}
else
{
return 0;
}
}

bool push(int x, int y)
{
if(stackPointer < stackSize - 1)
{
stackPointer++;
stack[stackPointer] = h * x + y;
return 1;
}
else
{
return 0;
}
}
void floodFill8Stack(int x, int y, int newColor, int oldColor)
{
if(newColor == oldColor) return; //avoid infinite loop
emptyStack();

if(!push(x, y)) return;
while(pop(x, y))
{
screenBuffer[x][y] = newColor;
if(x + 1 < w && screenBuffer[x + 1][y] == oldColor)
{
if(!push(x + 1, y)) return;
}
if(x - 1 >= 0 && screenBuffer[x - 1][y] == oldColor)
{
if(!push(x - 1, y)) return;
}
if(y + 1 < h && screenBuffer[x][y + 1] == oldColor)
{
if(!push(x, y + 1)) return;
}
if(y - 1 >= 0 && screenBuffer[x][y - 1] == oldColor)
{
if(!push(x, y - 1)) return;
}
if(x + 1 < w && y + 1 < h && screenBuffer[x + 1][y + 1] == oldColor)
{
if(!push(x + 1, y + 1)) return;
}
if(x + 1 < w && y - 1 >= 0 && screenBuffer[x + 1][y - 1] == oldColor)
{
if(!push(x + 1, y - 1)) return;
}
if(x - 1 >= 0 && y + 1 < h && screenBuffer[x - 1][y + 1] == oldColor)
{
if(!push(x - 1, y + 1)) return;
}
if(x - 1 >= 0 && y - 1 >= 0 && screenBuffer[x - 1][y - 1] == oldColor)
{
if(!push(x - 1, y - 1)) return;
}
}
}

或者去下面網址看看
http://hi..com/%B1%FE%CF%E6/blog/item/9014b7c3c8b52f100ff4775c.html

D. 我想用易語言填充畫板的指定區域 並計算填充了多少像素 怎麼計算

函數原型：BOOL ExtFloodFill(HDC hdc,int nXStart,int nYStart,COLORREF crColor,UINT fuFillType)；
參數：
nXSTart：指定要開始填充處的邏輯X軸坐標。
nYStart：指定要開始填充處的邏輯Y軸坐標。
crColor：指定要填充的邊界或區域的顏色。crColor的具體解釋要根據參數fuFillType的值而定。
fuFillType：指定要進行的填充操作類型。該參數必須是下列值之一，這些值的含義如下：
FLOODFILLBORDER：表示填充區域是由crColor參數指定的顏色包圍起來的部分。這種形式與FloodFill函數執行的填充類型一樣。
FLOODFILLSURFACE：表示填充區域是由crColor指定的顏色來定義。填充操作向四周伸展，直到遇到這種顏色為止。這種操作式樣對於帶有多種顏色邊界的填充區域有用。
返回值：如果函數執行成功，那麼返回值為非零；如果函數執行失敗，那麼返回值為零。若想獲得更多錯誤信息，請調用GetLastError函數。
備註：下列原因可能引起函數執行失敗：
填充無法完成。
指定的像素點有著參數crColor（如果要求
操作樣式）指定的邊界顏色（即顏色相同）。
指定的像素點沒有參數crColor（如果要求FLOODFILLSURFACE操作樣式）指定的顏色。
該點在剪輯區之外――也就是說在設備中不可見。
如果fuFillType參數為FLOODFILLBORDER，那麼系統認為要填充的區域是完全被參數crColor指定的顏色包圍起來的。該函數從參數nXStart和nYStart指定的點開始填充，向四周繼續，直到遇到邊界為止。
如果fuFillType是FLOODRILLSURFACE，那麼系統就認為要填充的區域是單顏色的，函數從nXStart和nYStart兩個參數指定的點開始填充區域，並向四周延伸，對包含參數crColor指定顏色的所有相鄰區域進行填充。
只有支持光柵顯示操作的設備和內存設備環境才支持ExtFloodFill函數。為了確定設備是否支持該技術，可使用函數GetDeviceCaps。
http://ke..com/link?url=5RPNfKX08273wPGa
以上內容復制自網路
常量值
FLOODFILLBORDER =0
FLOODRILLSURFACE =1

種子填充演算法
編輯
種子填充演算法又稱為邊界填充演算法。其基本思想是：從多邊形區域的一個內點開始，由內向外用給定的顏色畫點直到邊界為止。如果邊界是以一種顏色指定的，則種子填充演算法可逐個像素地處理直到遇到邊界顏色為止。
種子填充演算法常用四連通域和八連通域技術進行填充操作。
從區域內任意一點出發，通過上、下、左、右四個方向到達區域內的任意像素。用這種方法填充的區域就稱為四連通域；這種填充方法稱為四向連通演算法。
從區域內任意一點出發，通過上、下、左、右、左上、左下、右上和右下八個方向到達區域內的任意像素。用這種方法填充的區域就稱為八連通域；這種填充方法稱為八向連通演算法。
一般來說，八向連通演算法可以填充四向連通區域，而四向連通演算法有時不能填充八向連通區域。例如，八向連通填充演算法能夠正確填充如圖2.4a所示的區域的內部，而四向連通填充演算法只能完成如圖2.4b的部分填充。
圖2.4 四向連通填充演算法
a) 連通域及其內點 b) 填充四連通域
四向連通填充演算法：
a） 種子像素壓入棧中；
b） 如果棧為空，則轉e)；否則轉c)；
c） 彈出一個像素，並將該像素置成填充色；並判斷該像素相鄰的四連通像素是否為邊界色或已經置成多邊形的填充色，若不是，則將該像素壓入棧；
d） 轉b）；
e） 結束。
http://ke..com/link?url=jAM4UlhNMYk8__THzHZ2vN__KtQHm7CErVWq

要善用搜索