迷宫求解--栈的应用

0 人赞了该文章

实现截图为:

代码为:

#include <stdio.h>
#include <malloc.h>
typedef struct Loc
{
    int x;
    int y;
    int valid;//0表示未走过,1表示该点已经走过了
    int direction;//0表示向东,1表示向南,2表示向西,3表示向北
}loc;
typedef  struct sq_stack
{
    loc realLoc[100];
    int top;
}SqStack,*LinkSqStack;

void InitStack(LinkSqStack &S)
{
    S=(LinkSqStack)malloc(sizeof(SqStack));
    S->top=-1;
}
void Push(LinkSqStack &S,loc e)
{
    S->realLoc[++S->top]=e;
}
void Pop(LinkSqStack &S,loc &e)
{
    e=S->realLoc[S->top];
    --S->top;
}
int IsExited(LinkSqStack S,loc e)
{
    //在栈中是否存在元素e
    for(int i=0;i<=S->top;i++)
    {
        if(S->realLoc[i].x==e.x&&S->realLoc[i].y==e.y)
        {
            printf("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA");
            return 1;
        }
    }
    return 0;
}

loc nextPos(loc &cur,LinkSqStack S)
{
    int directionInfo=cur.direction;
    if(directionInfo==0)
    {
        ++cur.direction;
        int m=++cur.y;
        loc cur1={cur.x,m,0,0};
        if(IsExited(S,cur1)==1)
        {
            cur1.valid=1;
        }
        printf("向东为%d,%d\r\n",cur1.x,cur1.y);
        return cur1;
    }
    else if(directionInfo==1)
    {
        ++cur.direction;
        loc cur1={++cur.x,cur.y,0,0};
        if(IsExited(S,cur1)==1)
        {
            cur1.valid=1;
        }
        printf("向南为%d,%d\r\n",cur1.x,cur1.y);
        return cur1;
    }
    else if(directionInfo==2)
    {
        ++cur.direction;
        loc cur1={cur.x,--cur.y,0,0};
        printf("向西开始验证\r\n");
        if(IsExited(S,cur1)==1)
        {
            cur1.valid=1;
        }
        printf("向西为%d,%d,%d\r\n",cur1.x,cur1.y,cur1.valid);
        return cur1;
    }
    else if(directionInfo==3)
    {
        ++cur.direction;
        loc cur1={--cur.x,cur.y,0,0};
        if(IsExited(S,cur1)==1)
        {
            cur1.valid=1;
        }
        printf("向北为%d,%d\r\n",cur1.x,cur1.y);
        return cur1;
    }
    else
    {
        printf("产生错误\r\n");
        loc a={0,0,0,0};
        return a;
    }
}

void TravelPath(LinkSqStack &S)
{
    printf("------------------------------------------------------------------\r\n");
    for(int i=0;i<=S->top;i++)
    {
        printf("******存储的点的信息******\r\n");
        printf("坐标:(%d,%d)\r\n",S->realLoc[i].x,S->realLoc[i].y);
        printf("是否被标记过:%d\r\n",S->realLoc[i].valid);
        printf("当前方向:%d\r\n",S->realLoc[i].direction);
        printf("**************************\r\n");
    }
    printf("------------------------------------------------------------------\r\n");
}

void getPath(LinkSqStack &S,int map[10][10])
{
    loc start={1,1,0,0};
    loc end={8,8,0,0};
    loc cur=start;
    loc e;
    int m=0;
    do
    {
        if(cur.valid!=1&&map[cur.x][cur.y]!=1)
        {
            cur.valid=1;
            Push(S,cur);
            if(cur.x==end.y&&cur.y==end.y)
            {

                printf("已经找到出口\r\n");
                printf("走到出口的坐标为:\r\n");
                for(int i=0;i<=S->top;i++)
                    {
                        printf("(%d,%d)|",S->realLoc[i].x,S->realLoc[i].y);
                    }
                return;
            }
            printf("***********到下一个位置***********\r\n");
            TravelPath(S);
            cur=nextPos(cur,S);
        }
        else
        {
            if(S->top!=-1)
            {
                Pop(S,e);
                while(e.direction==3&&S->top!=-1)
                {
                    map[e.x][e.y]=1;//不能通过
                    Pop(S,e);
                }
                if(e.direction<3)
                {
                    e.direction++;
                    Push(S,e);
                    cur=nextPos(e,S);
                }
            }
        }

    }while(S->top!=-1);

}

void  main()
{
    LinkSqStack S;
    InitStack(S);
    int con[10][10]={
        {1,1,1,1,1,1,1,1,1,1},
        {1,0,0,1,0,0,0,1,0,1},
        {1,0,0,1,0,0,0,1,0,1},
        {1,0,0,0,0,1,1,0,0,1},
        {1,0,1,1,1,0,0,0,0,1},
        {1,0,0,0,1,0,0,0,0,1},
        {1,0,1,0,0,0,1,0,0,1},
        {1,0,1,1,1,0,1,1,0,1},
        {1,1,0,0,0,0,0,0,0,1},
        {1,1,1,1,1,1,1,1,1,1}
    };
    for(int i=0;i<10;i++)
    {
        for(int j=0;j<10;j++)
        {
            if(con[i][j]==1)
            {
                printf("■");
            }
            else
            {
                printf("□");
            }

        }
        printf("\r\n");
    }
    /*迷宫构建完成*/
    getPath(S,con);

}

评论

暂无评论