[栈和队列](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);变量内,我们来看这个函数

img

函数对应了两个循环,给矩阵内的单元赋值,第一个循环将所有x都赋予它的下标数,所有y都赋予它的下标数,所有的visited都赋予0,所有的Color都赋予0,图解如下

img

第二个循环将第2、3、4行的2、3列的颜色设置为3,如图

img

第三个循环将第5、6行的3、4、5列全部设为三,图解如下:

img

到这里,初始化就结束,我们继续进入主函数看下一步

将g数组传入ShowGraphArray(g);函数内,我们来看看这个函数的功能

img

输出所有单元的Color内容。输出看图就好,然后继续

img

定义了一个临时的posType类型的变量,x和y都为5,然后定义了一个fillcolor变量,表示指定更换的颜色,值为6,,进入核心函数RegionFilling函数内

img

下面的所有操作就是判断上下左右四个方向的颜色是否被访问过,如果没被访问过,以及新填充的颜色是否为以前已存在的颜色,如果是,则不将此坐标压入栈中,如果不是,则将此坐标压入栈中。

循环结束的条件为栈空,栈空就是上下左右四个方位全部走到了边界,已经全部填满,则不再走下去。

我们先看继续的代码片段,在来模拟这次的输入。

img

后边就是遍历整个数组,我们来模拟上述输出然后优化个我们看得懂的程序

鉴于上述的墙的颜色是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");
    }
}

运行结果:

img输入样例

输入如下:

img

本文链接:

https://nullcode.fun/25.html
1 + 1 =
快来做第一个评论的人吧~