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

要善用搜索