迷宫求解——栈的实现

た入场券 2022-05-31 01:06 242阅读 0赞

**一、题目及分析**

求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解决迷宫问题时,通常用的是“穷举求解”的方法,即从口出发,顺某方向向前探索,若能走通,则继续往前走;否则沿原入口路退回,换一个方向再继续探索,直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回,显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此,在求迷宫通路的算法中应用“栈”。也就是自然而然的事了。首先,在计算机中可以用如下图所示的方块图表 示迷宫。图中的每个方块或为通道(以空白方块表示), 或为墙(以带阴影线的方块表示)。所求路径必须是简 单路径,即在求得的路径上不能重复出现同一通道块。假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”,则求迷宫中一条路径的算法的基本思想是:若当前位置“可通”,则纳入“当前路径”,并继续朝位置”探索,即切换“下一位置”为“当前位置”,如此重复直至到达出口;若当前位置“不可通”,则应顺着“来向”退回到“前一通道块”,然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周4个方块均“不可通”则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周4个方向(东、南、西、北)上相邻的方块。假设以栈S记录”当前路径”,则栈顶中存放的是“当前路径上最后一个通道块”。由此,“纳入路径”的操作即为“当前位置入栈”;“从当前路径上删除前一通道块”的操作即为“出栈。

**二、思路**

![SouthEast][]![SouthEast 1][]

迷宫

![SouthEast 2][]

迷宫的文件存储方式

\#\#\#\#\#\#\#\#\#\#  
\#..\#...\#.\#  
\#..\#...\#.\#  
\#....\#\#..\#  
\#.\#\#\#....\#  
\#...\#....\#  
\#.\#...\#..\#  
\#.\#\#\#.\#\#.\#  
\#\#.......\#  
\#\#\#\#\#\#\#\#\#\#

**三、代码**

#include<stdio.h>
    #include<stdlib.h>
    #define length 10
    #define width 10
    #define start_hang 1 //从0行开始计算row
    #define start_lie 1//从0列开始column
    #define end_hang 8
    #define end_lie 8
    #define STACK_INIT_SIZE	length*width 
    char maze[width][length];
    typedef struct
    {
    	int r;
    	int c;
    }postype;
    typedef struct
    {
    	int ord;//通道块在路径上的序号
    	postype seat;//通道块在迷宫中的坐标
    	int di;//从此通道块走向下一通道块的方向 
    }selemtype; 
    typedef struct
    {
    	selemtype *base;
    	selemtype *top;
    	int stacksize;
    }sqstack;
    
    void initstack(sqstack *s)
    {
    	s->base=(selemtype *)malloc(STACK_INIT_SIZE*sizeof(selemtype));
    	if(!s->base)
    	{
    		printf("创建空间失败");
    		exit(0); 
    	}
    	s->top=s->base;
    	s->stacksize=STACK_INIT_SIZE;
    }
    
    void push(sqstack *s,selemtype e)
    {
    	if(s->top-s->base>s->stacksize)//本题中，这里可以不写，因为STACK_INIT_SIZE=length*width 
    	{
    		s->base=(selemtype *)realloc(s->base,(s->stacksize+2)*sizeof(selemtype));
    		if(!s->base)                // 当空间不足时，增加两个空间 
    		{
    			printf("栈增加空间失败");
    			exit(0); 
    		}
    		s->top=s->base+s->stacksize;
    		s->stacksize+=2;
    	}
    	*s->top++=e;//printf("$**");//检验入栈 
    }
    
    
    void readmaze()//从文件中读入迷宫 。用#表示墙壁，用.表示通路，重点用B表示 
    {
    	char ch;
    	int i,j;
    	FILE *fp;
    	fp=fopen("maze.txt","r");
    	if(fp==NULL)
    	{
    		printf("打开迷宫文件失败");
    		exit(0); 
    	}
    	for(i=0;i<width;i++)
    	{
    		for(j=0;j<length;j++)
    		{
    			ch=fgetc(fp);
    			maze[i][j]=ch;
    		}
    		ch=fgetc(fp);//用来接收换行符 
    	}
    	for(i=0;i<width;i++)
    	{
    		for(j=0;j<length;j++)
    		{
    			printf("%c",maze[i][j]);
    		}
    		printf("\n");//输出换行 
    	}
    } 
    
    int mazepath(sqstack *s,postype *start,postype *end)
    {
    	int footmark[length][width]={0};//走过但目前通的方块标记为1
    	int i=0;
    	selemtype e;
    	postype curpos,endpos;
    	curpos=*start;//printf("%d,%d",curpos.c,curpos.r);检查复制有无成功 
    	endpos=*end;
    	do
    	{       //可以通行且没有走过的情况下进栈 
    		if(maze[curpos.r][curpos.c]=='.'&&footmark[curpos.r][curpos.c]==0)
    		{
    			footmark[curpos.r][curpos.c]=1;
    			i++;
    			e.ord=i;
    			e.seat=curpos;
    			e.di=1;//初始化为1，默认将会向东走一步 
    			push(s,e);
    			if(curpos.r==endpos.r&&curpos.c==endpos.c)//求得路径存入栈中 
    				return 1;     //若当前为出口位置，则结束 
    			else
    				curpos.c++;//否则切换到当前位置的东邻方块作为新的当前位置 
    		}
    		else
    		{
    			curpos=e.seat;//当前道路不通，回归上一个位置 
    			if(e.di<4)//此时e虽然被复制进入栈中，但外面的e还没有改变 
    			{				         //若栈不空，且栈顶位置尚有其他位置未经探索
    				switch(e.di)         //每次都是对当前的位置curpos进行判断
    	 								//下面的循环就要注意对curpos进行更新 
    				{
    					case 1:curpos.r++;e.di++;break;//向下 
    					case 2:curpos.c--;e.di++;break;
    					case 3:curpos.r--;e.di++;break;
    					case 4:break;//四周不通 
    				}
    			}
    			else if(e.di==4)//栈不空，但栈顶周围均不通
    			{
    				s->top--;//从路径中删除该通道块；//这里要补上标记 
    				if(s->base!=s->top) //若栈不为空，重新测试新的栈顶 
    				{
    					e=*--s->top;//printf("@**");//验证出栈次数;
    					s->top++;//s->top总是指向栈顶，最上面元素的上一层，这里将s->top归位 
    					i--;//序号减一 
    					curpos=e.seat;//对当前位置进行更新 
    				} 
    			}						  
    		} 
    	}while(s->base!=s->top); 
    	return -1;//跳出循环说明没有路径
    } 
    
    void primazepath(sqstack *s)
    {			//printf("$*******"); 
    	selemtype e;
    	while(s->base!=s->top)
    	{
    		e=*--s->top;
    		printf("步数%d	位置%d,%d:\n",e.ord,e.seat.r,e.seat.c);
    	}	
    } 
    
    void main()
    {
    	int m=2;
    	sqstack s;
    	initstack(&s); 
    	readmaze();
    	postype start,end;
    	start.r=start_hang;
    	start.c=start_lie;
    	end.r=end_hang;
    	end.c=end_lie;
    	m=mazepath(&s,&start,&end);
    	//printf("%d",m);
    	if(m==-1)
    	{
    		printf("没有路径");
    		exit(0); 
    	} 
    	primazepath(&s);
    }

四、代码分析

1、文件读取字符的时候，要注意单独接收换行符，排除换行符的干扰。（详见c语言文件章节）

2、不能用指针返回在调用函数中创建的栈的地址。因为栈的生命周期和函数的周期相同。（具体的原因目前不清 楚）

3、结构体中如果含有指针元素，则在复制中存在浅拷贝问题。（即指针复制了地址，它们指向相同的空间。也即一个空间，两个地址，物理空间中的内容并没有开辟空间进行复制）。

**五、体会**

这是我目前写过最难的代码了。出了很多问题，也花了很多时间，中间也有焦躁。

保持一个平常心敲代码。踏踏实实的打好基础。

[SouthEast]: https://img-blog.csdn.net/20180202101259817?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvc2luYXRfMzg4MTY5MjQ=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: /images/20220531/60111517379a4b1093198223042e3d04.png
[SouthEast 2]: /images/20220531/58eaf3c26a45487eac37af095840a866.png