c语言实现 迷宫问题.doc

c语言实现 迷宫问题.doc

ID:48517289

大小:271.50 KB

页数:19页

时间:2020-01-26

c语言实现  迷宫问题.doc_第1页
c语言实现  迷宫问题.doc_第2页
c语言实现  迷宫问题.doc_第3页
c语言实现  迷宫问题.doc_第4页
c语言实现  迷宫问题.doc_第5页
资源描述:

《c语言实现 迷宫问题.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、.数据结构试验——迷宫问题(一)基本问题1.问题描述这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入,让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行,迷宫唯一的出口处放有一块奶酪,吸引老鼠找到出口。简而言之,迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图1所示。图1迷宫示意图迷宫四周设为墙;无填充处,为可通处。设每个点有四个可通方向,分别为东、南、西、北(为了清晰,以下称“上下左右”)。左上角为入口。右下角为出口。迷宫有一个入口,一个出口。设计程序求解迷宫的一条通路。2.

2、数据结构设计以一个m×n的数组mg表示迷宫,每个元素表示一个方块状态,数组元素0和1分别表示迷宫中的通路和障碍。迷宫四周为墙,对应的迷宫数组的边界元素均为1。根据题目中的数据,设置一个数组mg如下intmg[M+2][N+2]={{1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1},{1,1,0,0,0,1,1,1},{1,0,0,1,0,0,0,1},{1,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1}};在算法中用到的栈采用顺序存储结构,将栈定义为Struct{inti;//当前方块的行号int

3、j;//当前方块的列号intdi;//di是下一个相邻的可走的方位号}st[MaxSize];//定义栈..inttop=-1//初始化栈3设计运算算法要寻找一条通过迷宫的路径,就必须进行试探性搜索,只要有路可走就前进一步,无路可进,换一个方向进行尝试;当所有方向均不可走时,则沿原路退回一步(称为回溯),重新选择未走过可走的路,如此继续,直至到达出口或返回入口(没有通路)。在探索前进路径时,需要将搜索的踪迹记录下来,以便走不通时,可沿原路返回到前一个点换一个方向再进行新的探索。后退的尝试路径与前进路径正好相反,因此可以借用一个栈来记录

4、前进路径。方向:每一个可通点有4个可尝试的方向,向不同的方向前进时,目的地的坐标不同。预先把4个方向上的位移存在一个数组中。如把上、右、下、左(即顺时针方向)依次编号为0、1、2、3.其增量数组move[4]如图3所示。move[4]xy0-1010121030-1图2数组move[4]方位示意图如下:通路:通路上的每一个点有3个属性:一个横坐标属性i、一个列坐标属性j和一个方向属性di,表示其下一点的位置。如果约定尝试的顺序为上、右、下、左(即顺时针方向),则每尝试一个方向不通时,di值增1,当d增至4时,表示此位置一定不是通路上的

5、点,从栈中去除。在找到出口时,栈中保存的就是一条迷宫通路。(1)下面介绍求解迷宫(xi,yj)到终点(xe,ye)的路径的函数:先将入口进栈(其初始位置设置为—1),在栈不空时循环——取栈顶方块(不退栈)①若该方块为出口,输出所有的方块即为路径,其代码和相应解释如下:..intmgpath(intxi,intyi,intxe,intye)//求解路径为:(xi,yi)->(xe,ye){struct{inti;//当前方块的行号intj;//当前方块的列号intdi;//di是下一可走方位的方位号}st[MaxSize];//定义栈i

6、nttop=-1;//初始化栈指针inti,j,k,di,find;top++;//初始方块进栈st[top].i=xi;st[top].j=yi;st[top].di=-1;mg[1][1]=-1;while(top>-1)//栈不空时循环{i=st[top].i;j=st[top].j;di=st[top].di;//取栈顶方块if(i==xe&&j==ye)//找到了出口,输出路径{printf("迷宫路径如下:");for(k=0;k<=top;k++){printf("t(%d,%d)",st[k].i,st[k].j

7、);if((k+1)%5==0)//每输出每5个方块后换一行printf("");}printf("");return(1);//找到一条路径后返回1}②否则,找下一个可走的相邻方块若不存在这样的路径,说明当前的路径不可能走通,也就是恢复当前方块为0后退栈。若存在这样的方块,则其方位保存在栈顶元素中,并将这个可走的相邻方块进栈(其初始位置设置为-1)求迷宫回溯过程如图4所示..从前一个方块找到相邻可走方块之后,再从当前方块找在、相邻可走方块,若没有这样的方快,说明当前方块不可能是从入口路径到出口路径的一个方块,则从当前方块回溯

8、到前一个方块,继续从前一个方块找可走的方块。为了保证试探的可走的相邻方块不是已走路径上的方块,如(i,j)已经进栈,在试探(i+1,j)的下一方块时,又试探道(i,j),这样会很悲剧的引起死循环,为此,在一个方块进栈后,

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。