[栈和队列](3.1)洪水算法_DFS
题目答案为：
#include <iostream.h>
#include <stdlib.h>
typedef struct{
int x;
int y;
}PosType;
typedef struct{
int Color;
int Visited;
PosType seat;
}ElemType;
#include "d:\VC99\Stack.h"
#define M 8
#define N 8
ElemType g[M][N];
void CreateGDS(ElemType g[M][N]);
void ShowGraphArray(ElemType g[M][N]);
void RegionFilling(ElemType g[M][N],PosType CurPos,int NewColor);
int main()
{
CreateGDS(g);
ShowGraphArray(g);
PosType StartPos;
StartPos.x=5;
StartPos.y=5;
int FillColor=6;
RegionFilling(g,StartPos,FillColor);
cout<<endl;
ShowGraphArray(g);
return 0;
}
void RegionFilling(ElemType g[M][N],PosType CurPos,int FillColor)
{
Stack s;
InitStack(s);
ElemType e;
int OldColor=g[CurPos.x][CurPos.y].Color;
Push(s,g[CurPos.x][CurPos.y]);
while(!StackEmpty(s)){
Pop(s,e);
CurPos=e.seat;
g[CurPos.x][CurPos.y].Color=FillColor;
g[CurPos.x][CurPos.y].Visited=1;
if(CurPos.x<M &&
!g[CurPos.x+1][CurPos.y].Visited &&
g[CurPos.x+1][CurPos.y].Color==OldColor
)
Push(s,g[CurPos.x+1][CurPos.y]);
if(CurPos.x>0 &&
!g[CurPos.x-1][CurPos.y].Visited &&
g[CurPos.x-1][CurPos.y].Color==OldColor
)
Push(s,g[CurPos.x-1][CurPos.y]);
if(CurPos.y<N &&
!g[CurPos.x][CurPos.y+1].Visited &&
g[CurPos.x][CurPos.y+1].Color==OldColor
)
Push(s,g[CurPos.x][CurPos.y+1]);
if(CurPos.y>0 &&
!g[CurPos.x][CurPos.y-1].Visited &&
g[CurPos.x][CurPos.y-1].Color==OldColor
)
Push(s,g[CurPos.x][CurPos.y-1]);
}
}
void CreateGDS(ElemType g[M][N])
{
int i,j;
for(i=0;i<M;i++)
for(j=0;j<N;j++){
g[i][j].seat.x=i;
g[i][j].seat.y=j;
g[i][j].Visited=0;
g[i][j].Color=0;
}
for(i=2;i<5;i++)
for(j=2;j<4;j++)
g[i][j].Color=3;
for(i=5;i<M-1;i++)
for(j=3;j<6;j++)
g[i][j].Color=3;
}
void ShowGraphArray(ElemType g[M][N])
{
int i,j;
for(i=0;i<M;i++){
for(j=0;j<N;j++)
cout<<g[i][j].Color;
cout<<endl;
}
}首先它开了一个8*8的矩阵，所有操作都在矩阵内进行，我们对应矩阵来看看
首先它把数组g传入了CreateGDS(g);变量内，我们来看这个函数
函数对应了两个循环，给矩阵内的单元赋值，第一个循环将所有x都赋予它的下标数，所有y都赋予它的下标数，所有的visited都赋予0，所有的Color都赋予0，图解如下
第二个循环将第2、3、4行的2、3列的颜色设置为3，如图
第三个循环将第5、6行的3、4、5列全部设为三，图解如下：
到这里，初始化就结束，我们继续进入主函数看下一步
将g数组传入ShowGraphArray(g);函数内，我们来看看这个函数的功能
输出所有单元的Color内容。输出看图就好，然后继续
定义了一个临时的posType类型的变量，x和y都为5，然后定义了一个fillcolor变量，表示指定更换的颜色，值为6,，进入核心函数RegionFilling函数内
下面的所有操作就是判断上下左右四个方向的颜色是否被访问过，如果没被访问过，以及新填充的颜色是否为以前已存在的颜色，如果是，则不将此坐标压入栈中，如果不是，则将此坐标压入栈中。
循环结束的条件为栈空，栈空就是上下左右四个方位全部走到了边界，已经全部填满，则不再走下去。
我们先看继续的代码片段，在来模拟这次的输入。
后边就是遍历整个数组，我们来模拟上述输出然后优化个我们看得懂的程序
鉴于上述的墙的颜色是3，我们用粉色来代替，然后指定需要更新的颜色是6，我们用黄色来代替。
给定的坐标是g(5,5)，方向是东西南北。
而下一次循环取栈顶元素就是从最后一次压入栈中的坐标开始。演示如下：
根据上述思路，我们可以写出C的核心功能函数
void RegioFilling(Filli* F, int M, int N)
{
InitStack(&S);
printf("请选择给定坐标：");
BOX ColorX, temp, temp2;
scanf_s("%d,%d", &ColorX.x, &ColorX.y);
printf("请输入需要填充的颜色：");
int color;
scanf_s("%d", &color);
if (ColorX.x >= 0 && ColorX.x <= N && ColorX.y >= 0 && ColorX.y <= N)
{
Push(&S, ColorX);
while (S.top > S.base && color != 0)
{
Pop(&S, &temp);
F->a[temp.x][temp.y] = color;
if (temp.x >= 0 && temp.x < M && temp.x - 1 >= 0 && temp.y >= 0 && temp.y < N && F->a[temp.x - 1][temp.y] == 0)
{
F->a[temp.x - 1][temp.y] = color;
temp2.x = temp.x - 1;
temp2.y = temp.y;
Push(&S, temp2);
}
if (temp.x >= 0 && temp.x < M && temp.x + 1 < M && temp.y >= 0 && temp.y < N && F->a[temp.x + 1][temp.y] == 0)
{
F->a[temp.x + 1][temp.y] = color;
temp2.x = temp.x + 1;
temp2.y = temp.y;
Push(&S, temp2);
}
if (temp.x >= 0 && temp.x < M && temp.y >= 0 && temp.y < N &&temp.y - 1 >= 0 && F->a[temp.x][temp.y - 1] == 0 )
{
F->a[temp.x][temp.y - 1] = color;
temp2.x = temp.x;
temp2.y = temp.y-1;
Push(&S, temp2);
}
if (temp.x >= 0 && temp.x < M && temp.y >= 0 && temp.y < N &&temp.y + 1 < N && F->a[temp.x][temp.y + 1] == 0)
{
F->a[temp.x][temp.y + 1] = color;
temp2.x = temp.x;
temp2.y = temp.y+1;
Push(&S, temp2);
}
visit(F, M, N);
visitStack();
printf("\n");
}
}
else
{
printf("溢出\n");
}
}这儿需要注意的是，每次访问的时候需要划定好边界，从左到右全部为帧才执行。不仅要判断当前坐标的是否过节，还需要判断下一坐标是否过界。
墙在初始化的时候可以自定义，也可以利用随机数不超过边界生成。
完整测试代码如下：
#define STACKMAX 100
#include<stdio.h>
#include<stdio.h>
#include<string.h>
typedef struct
{
int x, y;
}BOX;
typedef struct
{
BOX* base;
BOX* top;
}SqStack;
typedef struct
{
int** a;
}Filli;
Filli F;
SqStack S;
void FilliInit(Filli* F, int M, int N);
void visitStack();
void visit(Filli* F, int M, int N);
void InitStack(SqStack* S);
void RegioFilling(Filli* F, int M, int N);
void Push(SqStack* S, BOX temp);
void Pop(SqStack* S ,BOX* temp);
int main()
{
int m, n;
printf("请给定矩阵行：");
scanf_s("%d", &m);
printf("请给定矩阵宽：");
scanf_s("%d", &n);
FilliInit(&F, m, n);
RegioFilling(&F, m, n);
system("pause");
return 0;
}
void FilliInit(Filli *F,int M,int N)
{
F->a = (int**)malloc(sizeof(int*) * M);
for (int i = 0; i < M; i++)
{
*(F->a + i) = (int*)malloc(sizeof(int) * N);
for (int j = 0; j < N; j++)
{
*(*(F->a + i) + j) = 0;
}
}
/*在这里定义墙*/
int x = rand() % M;
int y = rand() % N;
int oldColor;
printf("请输入随机颜色：");
scanf_s("%d", &oldColor);
for (int i = x; i < M-1; i++)
{
for (int j = y; j < N-1; j++)
{
*(*(F->a + i) + j) = oldColor;
}
}
visit(F, M, N);
printf("成功\n");
}
void InitStack(SqStack* S)
{
S->base = (BOX*)malloc(sizeof(BOX) * STACKMAX);
if (S->base == NULL)
{
exit(0);
}
S->top = S->base;
}
void Push(SqStack* S, BOX temp)
{
S->top->x = temp.x;
S->top->y = temp.y;
S->top++;
}
void Pop(SqStack* S, BOX* temp)
{
S->top--;
temp->x = S->top->x;
temp->y = S->top->y;
}
void visit(Filli *F,int M,int N)
{
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
printf("%d", *(*(F->a + i) + j));
}
printf("\n");
}
}
void visitStack()
{
BOX* p = S.base;
while (p < S.top)
{
printf("%d,%d ", p->x, p->y);
p++;
}
}
void RegioFilling(Filli* F, int M, int N)
{
InitStack(&S);
printf("请选择给定坐标：");
BOX ColorX, temp, temp2;
scanf_s("%d,%d", &ColorX.x, &ColorX.y);
printf("请输入需要填充的颜色：");
int color;
scanf_s("%d", &color);
if (ColorX.x >= 0 && ColorX.x <= N && ColorX.y >= 0 && ColorX.y <= N)
{
Push(&S, ColorX);
while (S.top > S.base && color != 0)
{
Pop(&S, &temp);
F->a[temp.x][temp.y] = color;
if (temp.x >= 0 && temp.x < M && temp.x - 1 >= 0 && temp.y >= 0 && temp.y < N && F->a[temp.x - 1][temp.y] == 0)
{
F->a[temp.x - 1][temp.y] = color;
temp2.x = temp.x - 1;
temp2.y = temp.y;
Push(&S, temp2);
}
if (temp.x >= 0 && temp.x < M && temp.x + 1 < M && temp.y >= 0 && temp.y < N && F->a[temp.x + 1][temp.y] == 0)
{
F->a[temp.x + 1][temp.y] = color;
temp2.x = temp.x + 1;
temp2.y = temp.y;
Push(&S, temp2);
}
if (temp.x >= 0 && temp.x < M && temp.y >= 0 && temp.y < N &&temp.y - 1 >= 0 && F->a[temp.x][temp.y - 1] == 0 )
{
F->a[temp.x][temp.y - 1] = color;
temp2.x = temp.x;
temp2.y = temp.y-1;
Push(&S, temp2);
}
if (temp.x >= 0 && temp.x < M && temp.y >= 0 && temp.y < N &&temp.y + 1 < N && F->a[temp.x][temp.y + 1] == 0)
{
F->a[temp.x][temp.y + 1] = color;
temp2.x = temp.x;
temp2.y = temp.y+1;
Push(&S, temp2);
}
visit(F, M, N);
visitStack();
printf("\n");
}
}
else
{
printf("溢出\n");
}
}运行结果：
输入样例
输入如下：
