数据结构——迷宫

àì夳堔傛蜴生んèń 2022-04-22 02:22 253阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    
    #define SIZE 100             //数组行列的最大范围
    #define STACT_INIT_SIZE 100 //存储空间初始分配量
    #define STACKINCREMENT 100  //存储空间分配增量
    
    typedef struct
    {
    	int x;
    	int y;         //通道块在迷宫中的"坐标位置";
    	int di;        //从此通道块走向下一个通道块的位置；
    }POS;             
    
    typedef struct
    {
    	POS *base;   
    	POS *top;
    	int stacksize;
    }SqStack;
    
    
    //函数原型：
    int InitStack(SqStack &s);      //构建空栈函数；
    int Push(SqStack &s,POS m);     //元素入栈函数
    POS Pop(SqStack &s);            //元素出栈函数
    //寻找起点终点函数
    int	fond_start_end(POS &start,POS &end,int ditu[SIZE][SIZE],int n,int m);
    int Pass(POS curpos,int ditu[SIZE][SIZE]);  //判断当前位置是否可走函数
    void Mark(POS curpos,int ditu[SIZE][SIZE],int n);       //修改地图函数
    int MazePath(int ditu[SIZE][SIZE],POS start,POS end);
    POS  NextPos(POS &curpos);  //去下一个点函数
    int StackEmpty(SqStack S);  //判断空栈函数
    void Print(int diti[SIZE][SIZE],int n,int m); //打印迷宫函数
    void Scanf(int ditu[SIZE][SIZE],int n,int m); //存储迷宫函数
    void  shuoming();    //程序说明函数
    
    //主函数
    int main()
    {
    	int ditu[SIZE][SIZE]={0};
    	int n,m;
    	POS start,end;
    	shuoming();
    	printf("\n请输入迷宫的行数和列数: ");
    	scanf("%d %d",&n,&m);
    	Scanf(ditu,n,m);           //调用存储迷宫函数
    	fond_start_end(start,end,ditu,n,m);//寻找起点,终点函数
    	if(MazePath(ditu,start,end)==0) //迷宫函数
    	printf("呜呜,走不出这个迷宫了!\n\n");
    	else printf("哈哈,我走出迷宫啦!\n\n");
    	Print(ditu,n,m);   //调用打印迷宫函数
    	return 0;
    }
    
    int MazePath(int ditu[SIZE][SIZE],POS start,POS end)
    {
    	POS curpos;  //声明一个当前位置点
        POS e;
    	SqStack S;   //声明了一个名为S的栈，用于存储现在所在的坐标
    	InitStack(S);  //调用创建空栈函数
    	curpos=start;  //将起点赋给当前位置点
    	do
    	{
    		if(Pass(curpos,ditu))
    		{
    			curpos.di=0;
    			Mark(curpos,ditu,3);
    			Push(S,curpos);
    			if(curpos.x==end.x && curpos.y==end.y) return 1;
    			curpos=NextPos(curpos);
    			//curstep++;
    		}
    		else
    		{
    			if(!StackEmpty(S))
    			{
    				e=Pop(S);
    				while(e.di==4 && !StackEmpty(S))
    				{
    					Mark(e,ditu,4);
    					e=Pop(S);
    				}//while
    				if(e.di<4)
    				{
    					e.di++;
    					Push(S,e);
    					curpos=NextPos(e);
    				}//if
    			}//if
    		}//else
    	}while(!StackEmpty(S));
        return 0;
    }
    
    //*********************寻找起点终点函数****************
    int	fond_start_end(POS &start,POS &end,int ditu[SIZE][SIZE],int n,int m)
    {
    	int i,j;
        for(i=0;i<n;i++)
    	{
    		for(j=0;j<m;j++)
    		{
    			if(ditu[i][j]==2)
    			{
    				start.x=i;
    				start.y=j;
    				start.di=0;
    				//printf("x1=%d,y1=%d\n",start.x,start.y);
    			}
    			if(ditu[i][j]==5)
    			{
    				end.x=i;
    				end.y=j;
    				end.di=0;
    				//printf("x2=%d,y2=%d\n",end.x,end.y);
    			}
    		}
    	}
    	return 1;
    }
    //****************判断当前位置是否可走函数****************
    int Pass(POS curpos,int ditu[SIZE][SIZE])
    {
       // printf("%d %d=%d\n",curpos.x,curpos.y,ditu[curpos.x][curpos.y]);
    	if(ditu[curpos.x][curpos.y]==0 ||ditu[curpos.x][curpos.y]==2 || ditu[curpos.x][curpos.y]==5) return 1;
    	else return 0;
    }
    
    
    //***************修改地图********************
    void Mark(POS curpos,int ditu[SIZE][SIZE],int n)
    {
    	ditu[curpos.x][curpos.y]=n; 
    }
    
    //***********去下一个点函数***********
    POS  NextPos(POS &curpos)
    {
    	if(curpos.di==0)	curpos.y+=1;  //0表示还没有走过了，列+1表示向右走
        if(curpos.di==1)  	curpos.x+=1;  //1表示右已经走过了, 行+1表示向下走
        if(curpos.di==2)	curpos.y-=1;  //2表示下已经走过了, 列-1表示向左走
    	if(curpos.di==3)	curpos.x-=1;  //3表示左已经走过了，行-1表示向上走
    	return curpos;
    }
    
    //**********构造空栈函数************
    int InitStack(SqStack &s)
    {
    	//请求分配STACT_INIT_SIZE个POS类型的空间来作为栈；
        s.base=(POS*)malloc(STACT_INIT_SIZE*sizeof(POS));
    	if(!s.base) exit(0);  //判断申请空间内存是否成功；
    	s.top=s.base;          //将栈顶指针也指向栈底指针，表示空栈；
    	//将申请分配的栈当前的空间个数存进s.stacksize
    	s.stacksize=STACT_INIT_SIZE;   
    	return 1;
    }
    
    //************判断空栈函数**************
    int StackEmpty(SqStack s)
    {
    	if(!s.base) exit(0); //判断栈是否存在
    	if(s.top==s.base)    //判断是否是空栈
    	{
    		//printf("栈已经为空了\n");
    		return 1;
    	}
    	else return 0;
    }
    
    //************元素入栈函数***********
    int Push(SqStack &s,POS m)
    {
    	POS *new_p=NULL;
    	if(!s.base) exit(0); //判断栈是否存在
    	//判断是否没有内存来存新元素；
    	//若是内存不顾就用realloc（）函数重新申请内存；
    	//将新分配的内存地址放在new_p中，若申请成功再将new_p赋给栈底指针;
    	//避免原来的栈底指针丢失；
    	if(s.base-s.top>=s.stacksize)  
    	{
    	    new_p=(POS*)realloc(s.base,(STACT_INIT_SIZE+STACKINCREMENT)*sizeof(POS));
    		if(!new_p)
    		{
    			printf("重新申请内存分配失败！");
    			exit(0);
    		}
    	    s.base=new_p;
    		s.top=s.base+STACKINCREMENT; //用首地址加偏移量找到栈顶指针；
    		s.stacksize+=STACT_INIT_SIZE;//更新栈空间的大小；
    	}
    	(*s.top)=m; //将新元素压进栈顶；
    	s.top++;  //栈顶指针往上移；
        return 0;
    }
    
    //************元素出栈函数***********
    POS Pop(SqStack &s)
    {
    	POS m;
    	if(!s.base) exit(0); //判断栈是否存在；
    	if(s.top==s.base)    //判断是否是空栈
    	{
    		printf("栈已经为空了\n");
    		exit(0);
    	}
    	s.top--;   //让栈顶指针指向栈中最后一个元素
    	m=*s.top;  //把栈中最后一个元素存进m中；
    	return m;
    }
    
    //*************打印地图函数*************
    void Print(int ditu[SIZE][SIZE],int n,int m)
    {
    	int i,j;
    	printf("走迷宫路线:\n");
    	for(i=0;i<n;i++)
    	{
    		for(j=0;j<m;j++)
    		{
    			printf("%d ",ditu[i][j]);
    		}
    		printf("\n");
    		}
    	printf("\n");
    }
    
    //*************存储地图函数**************
    void Scanf(int ditu[SIZE][SIZE],int n,int m)
    {
    	int i,j;
    	printf("请输入地图:\n");
    	for(i=0;i<n;i++)
    	{
    		for(j=0;j<m;j++)
    		{
    			scanf("%d",&ditu[i][j]);
    		}
    	}
    }
    
    //***********程序说明********************
    void  shuoming()
    {
    	printf("\n      哈哈,欢迎来到小梅梅的迷宫基地      \n");
    	printf("------------------------------------------\n");
    	printf("| 程序功能:用户输入迷宫地图,打印迷宫路线! |\n");
    	printf("| 输入要求:1.输入迷宫的行列数,用空格隔开! |\n");
    	printf("|          2.输入迷宫地图;                |\n");
    	printf("| 用户注意:1----表示墙,不可走;	          |\n");
    	printf("|          2----表示起点;                 |\n");
    	printf("|          3----表示走出迷宫路线;         |\n");
    	printf("|          4----表示此路是死胡同;         |\n");
    	printf("|          5----表示终点;                 |\n");
    	printf("------------------------------------------\n");
    						   
    
    }
    
    
    /* 迷宫图1
    1 1 1 1 1 1 1 1 1 1
    1 2 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 5 1
    1 1 1 1 1 1 1 1 1 1
    */
    
    /* 迷宫图2
    1 1 1 1 1
    1 2 1 5 1
    1 0 1 1 1
    1 0 0 0 1
    1 1 1 1 1
    */
    
    /*
    1 1 1 1 1 1 1 1 1 1
    1 0 0 0 2 0 0 5 0 1
    1 0 0 0 0 0 1 0 0 1
    1 0 0 0 0 0 1 1 0 1
    1 0 0 1 1 1 0 1 0 1
    1 0 0 1 1 0 0 1 1 1
    1 1 1 0 0 0 0 1 0 1
    1 0 0 0 0 0 0 0 0 1
    1 0 1 0 1 0 0 0 1 1
    1 1 1 1 1 1 1 1 1 1
    */
    
    /*
    1 1 1 1 1 1 1 1 1 1
    1 0 0 0 2 0 1 5 0 1
    1 0 0 0 0 0 1 0 0 1
    1 0 0 0 0 0 1 1 0 1
    1 0 0 1 1 1 0 0 0 1
    1 0 0 1 1 0 0 0 1 1
    1 0 1 0 0 0 0 1 0 1
    1 0 0 0 0 0 0 0 0 1
    1 0 1 0 1 0 0 0 1 1
    1 1 1 1 1 1 1 1 1 1
    */