基于队列和哈希的种⼦填充算法下⾯是效果图：
核⼼代码如下：虽然看起来很多，但是相同的内容很多，逻辑清晰。
void fillArea(int x,int y)
{
COLORREF color =getpixel(x, y);//获取替换颜⾊
COLORREF paintColor =getfillcolor();//获取填充颜⾊
const int maxWidth =640;
const int maxHeight =480;
char filled[maxWidth * maxHeight]={0};//散列表，散列函数 h(key) = key.x + key.y * maxWidth  Queue queue;
queue.push(x, y);
while(!queue.isEmpty())
{
Node* node = queue.pop();
if(node->x <0|| node->x >= maxWidth || node->y <0|| node->y >= maxHeight)
{
delete node;
continue;//限制边界
}
//后继
int xT = node->x;int yT = node->y -1;
int xB = node->x;int yB = node->y +1;
int xL = node->x -1;int yL = node->y;
int xR = node->x +1;int yR = node->y;
COLORREF colorT =getpixel(xT, yT);
COLORREF colorB =getpixel(xB, yB);
COLORREF colorL =getpixel(xL, yL);
COLORREF colorR =getpixel(xR, yR);
int keyT = xT + yT * maxWidth;
int keyB = xB + yB * maxWidth;
int keyL = xL + yL * maxWidth;
int keyR = xR + yR * maxWidth;
if(colorT != paintColor && colorT == color && filled[keyT]!=1)
{
queue.push(xT, yT);
filled[keyT]=1;
}
if(colorB != paintColor && colorB == color && filled[keyB]!=1)
{
queue.push(xB, yB);
filled[keyB]=1;
}
if(colorL != paintColor && colorL == color && filled[keyL]!=1)
{
queue.push(xL, yL);
filled[keyL]=1;
}
if(colorR != paintColor && colorR == color && filled[keyR]!=1)
{
queue.push(xR, yR);
filled[keyR]=1;
}
//消已
putpixel(node->x, node->y, paintColor);
delete node;
}
}
代码解释：
类似于树的层序遍布，这⾥利⽤了⼀个 队列结构。
开始时，将种⼦点压⼊。
每当填充并删除⼀个种⼦时，将其周围的没有填充的点作为 新的种⼦ 压⼊队列中。
队列结构是我⾃⼰写的，如下：
struct Node
{
Node* next;
int x;
int y;
Node()
{
x =0;
y =0;
next =0;
}
Node(int x,int y)
{
this->x = x;
this->y = y;
this->next =0;
}
};
struct Queue
{
Node* head;
Node* tail;
Queue()
{
head = tail =new Node;
}
void push(int x,int y)
{
tail->next =new Node(x, y);
tail = tail->next;
}
Node*pop()
{
if(!isEmpty())
{
Node* temp = head->next;
head->next = head->next->next;
if(head->next ==0)
{
tail = head;
}
return temp;
}
return0;
}
种子哈希转换链接bool isEmpty()
{
return head == tail;
}
};
有同学可能对完整代码感兴趣。我也顺便附上吧。
这个程序引⽤了⼀个简单的图形库 easyx ⼤家可以百度去官⽹下载。
#include<iostream>
#include<graphics.h>
using namespace std;
//队列
struct Node
{
Node* next;
int x;
int y;
Node()
{
{
x =0;
y =0;
next =0;
}
Node(int x,int y)
{
this->x = x;
this->y = y;
this->next =0;
}
};
struct Queue
{
Node* head;
Node* tail;
Queue()
{
head = tail =new Node;
}
void push(int x,int y)
{
tail->next =new Node(x, y);
tail = tail->next;
}
Node*pop()
{
if(!isEmpty())
{
Node* temp = head->next;
head->next = head->next->next;
if(head->next ==0)
{
tail = head;
}
return temp;
}
return0;
}
bool isEmpty()
{
return head == tail;
}
};
void fillArea(int x,int y)
{
COLORREF color =getpixel(x, y);//获取替换颜⾊
COLORREF paintColor =getfillcolor();//获取填充颜⾊
const int maxWidth =640;
const int maxHeight =480;
char filled[maxWidth * maxHeight]={0};//散列表，散列函数 h(key) = key.x + key.y * maxWidth  Queue queue;
queue.push(x, y);
while(!queue.isEmpty())
{
Node* node = queue.pop();
if(node->x <0|| node->x >= maxWidth || node->y <0|| node->y >= maxHeight)
{
delete node;
continue;//限制边界
}
//后继
int xT = node->x;int yT = node->y -1;
int xB = node->x;int yB = node->y +1;
int xL = node->x -1;int yL = node->y;
int xR = node->x +1;int yR = node->y;
COLORREF colorT =getpixel(xT, yT);
COLORREF colorB =getpixel(xB, yB);
COLORREF colorL =getpixel(xL, yL);
COLORREF colorR =getpixel(xR, yR);
int keyT = xT + yT * maxWidth;
int keyB = xB + yB * maxWidth;
int keyL = xL + yL * maxWidth;
int keyR = xR + yR * maxWidth;
if(colorT != paintColor && colorT == color && filled[keyT]!=1) {
queue.push(xT, yT);
filled[keyT]=1;
}
if(colorB != paintColor && colorB == color && filled[keyB]!=1) {
queue.push(xB, yB);
filled[keyB]=1;
}
if(colorL != paintColor && colorL == color && filled[keyL]!=1) {
queue.push(xL, yL);
filled[keyL]=1;
}
if(colorR != paintColor && colorR == color && filled[keyR]!=1) {
queue.push(xR, yR);
filled[keyR]=1;
}
//消已
putpixel(node->x, node->y, paintColor);
delete node;
}
}
int main()
{
initgraph(640,480,1);
setfillcolor(0xffffff);
fillrectangle(0,0,640,480);
bool isDown =false;
MOUSEMSG msg;
int lastX;
int lastY;
while(true)
{
BeginBatchDraw();
while(MouseHit())
{
msg =GetMouseMsg();
if(msg.uMsg == WM_LBUTTONDOWN)
{
isDown =true;
lastX = msg.x;
lastY = msg.y;
}
if(msg.uMsg == WM_LBUTTONUP)
{
isDown =false;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。