(最新整理)迷宫问题的C,C++算法实现

1、(完整)迷宫问题的c,c+算法实现(完整)迷宫问题的c,c+算法实现 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（(完整)迷宫问题的c,c+算法实现）的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快 业绩进步，以下为(完整)迷宫问题的c,c+算法实现的全部内容。基于栈的c语言迷宫问题与实现一 问题描述多年以来,迷宫问题一直是令人感兴趣的题

2、目。实验心理学家训练老鼠在迷宫中寻找食物。许多神秘主义小说家也曾经把英国乡村花园迷宫作为谋杀现场。于是,老鼠过迷宫问题就此产生，这是一个很有趣的计算机问题，主要利用 “栈”是老鼠通过尝试的办法从入口穿过迷宫走到出口。迷宫只有两个门，一个叫做入口,另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题,即找出从入口到出口的路径。一个迷宫可用上图所示方阵m,n表示，0表示能通过，1 表示不能通过。现假设耗子从左上角1,1进入迷宫，编写算法,寻求一条从右下角m,n

3、 出去的路径.下图是一个迷宫的示意图:二 算法基本思想迷宫求解问题是栈的一个典型应用。基本算法思想是：在某个点上，按照一定的顺序（在本程序中顺序为上、右、下、左）对周围的墙、路进行判断(在本程序中分别用1、0)代替，若周围某个位置为0,则移动到该点上，再进行下一次判断；若周围的位置都为1（即没有通路），则一步步原路返回并判断有无其他通路，然后再次进行相同的判断，直到走到终点为止，或者确认没有任何通路后终止程序。要实现上述算法，需要用到栈的思想。栈里面压的是走过的路径,若遇到死路,则将该位置（在栈的顶层)弹出，再进行下一次判断；若遇到通路，则将该位置压栈并进行下一次判断。如此反复循环，直到程序结

4、束。此时，若迷宫有通路,则栈中存储的是迷宫通路坐标的倒序排列，再把所有坐标顺序打印后,即可得到正确的迷宫通路。三 程序具体部分的说明1. 迷宫的生成根据题目的要求，迷宫的大小是自定义输入的.所以在程序中用malloc申请动态二维数组。数组中的元素为随机生成的0、1。数组周围一圈的元素全部定义为1,以表示边界。2. 栈的c语言实现为了实现栈的功能，即清空、压栈、弹出、返回栈顶元素，在程序中编写了相应的函数。makenull 清空栈push 将横、纵坐标压栈topx 返回栈顶存储的横坐标topy 返回栈顶存储的纵坐标pop 弹出栈顶元素3. 具体的判断算法当位置坐标（程序中为x y)移到某一位置时

5、，将这个位置的值赋值为1并压栈，以说明该点已经走过。接着依次判断该点的上、右、下、左是否为0，若有一方为0，则移动到该位置上，进行下次判断;若为周围位置全部是1，则将该点压栈后不断弹出，每次弹出时判断栈顶元素(即走过的路)周围有无其他通路。如果有的话，则选择该方向继续走下去;如果栈已经为空仍然没有找到出路，则迷宫没有出口程序结束。当x y走到出口坐标时，程序判断部分结束。栈里面存储的是每个走过的点的坐标,将这些横纵坐标分别存储在两个数组中，最后将数组中的坐标元素倒序输出，即得到了完整的路径.四 程序源代码及注释 / maze.cpp ： 定义控制台应用程序的入口点./include stdaf

6、x.h”includestdio。h#includestring.h#include #includetime.htypedef int elementtype；struct nodeelementtype val1;elementtype val2； node *next;/定义结构体typedef node maze；void makenull(maze &s）;void push(elementtype x,elementtype y, maze s）；void pop（maze s);elementtype topx(maze s)；elementtype topy（maze s);/

7、申明函数int _tmain（int argc, _tchar argv)int p,q，x1，y1，i，j,k，n1，n2,m1，m2，l,w,max;int x,y;int a,b,c,d； printf(”输入迷宫长度及宽度l和wn”)； scanf(”d %d，l，&w);getchar();n1=w+2;n2=l+2;/为迷宫加上边界max=n1*n2; p=(int)malloc（n1sizeof（int)）; for(i=0；in1；i+） pi=(int *)malloc(n2*sizeof（int)；/生成二维动态数组 srand(time(null)；x1=（int*)ma

8、lloc(maxsizeof（int）;/生成动态数组用于存储路径y1=（int ）malloc（maxsizeof（int）)；/生成动态数组用于存储路径 for(i=0;imax；i+) x1i=0;for（i=0;imax；i+） y1i=0；/先将存储路径的数组元素全赋值为0 for(i=0；in1;i+) for(j=0；jn2；j+） if(i=0 | j=0） pij=1； else if（i=n1-1 | j=n2-1） pij=1; else pij=rand()2+0; /生成二维1 0随机数组p11=0;pn1-2n2-2=0;/定义迷宫的入口及出口 printf（生成的

9、迷宫如下(代表墙0代表路）：n)； for（i=0；i=0;) if（x1i!=0 & （x1i!=x1i1 | y1i！=y1i1) printf（%d ，d ，x1i，y1i)； i-; else if（x1i!=0 & （x1i=x1i1 & y1i=y1i1）) printf（ ”，x1i，y1i); i=i-2； else i;/倒序打印数组得到顺序出路坐标printf(,n1-2，n2-2);/打印出口坐标 getchar();return 0；void makenull（maze s) /清空栈的函数s = new node；s-next = null；void push(ele

10、menttype x，elementtype y， maze s）/压栈函数maze stk;stk = new node；stkval1 = x;stkval2 = y；stknext = snext;s-next = stk；void pop(maze s）/弹出函数maze stk；if(snext)stk = snext；snext = stknext；delete stk；elementtype topx(maze s）/返回横坐标函数if（s-next)return(s-next-val1)；elsereturn null；elementtype topy（maze s)/返回纵坐

11、标函数if(s-next）return(s-nextval2）;elsereturn null；另一种方法实现的迷宫代码#ifndef mmigong_hdefine mmigong_h#define max_size 100includeusing namespace std；struct nodeint x；int y;int di；;class stackprivate:int rrow;int ccolm;int top;int count;int minlenght；node stackmax_size;node sstackmax_size；public：stack（)； /初始化

12、/int insortmigong(); /输入迷宫（即一个二维数组)void findpath（int ab10); /找出迷宫的出路；stack:：stack（) /初始化rrow=0；ccolm=0;top=-1；count=1;minlenght=max_size；/*int * stack:：insortmigong(） /输入迷宫(即一个二维数组）int row=1,colm=1;while(true)cout”请输入迷宫的行数和列数：;cinrowcolm;if（row=0|colm=0）cout”输入错误!请重新输入:endl;rrow=row；ccolm=colm；conti

13、nue；elserrow=row；ccolm=colm；break;int mg；coutmgij;return mg；*/void stack:findpath（int ab10) /找出迷宫的出路int a,b，di,find，k;top+;stacktop。x=1;stacktop。y=1;stacktop.di=-1；ab11=-1；while（top1)a=stacktop。x；b=stacktop。y;di=stacktop。di;if（a=8&b=8)coutcount+”:”endl;for（int k=0；k=top；k+）cout”(stackk.x”，stackk。y”)

14、;if(！（(k+1）%15）)coutendl；coutendl;if（top+1minlenght）for(k=0；k=top；k+)sstackk=stackk;minlenght=top+1;abstacktop.xstacktop.y=0；top-；a=stacktop。x;b=stacktop。y；di=stacktop。di；find=0;while（di8！find)di+;switch（di)case 0:a=stacktop.x-1;b=stacktop.y；break；case 1：a=stacktop.x;b=stacktop.y+1;break；case 2：a=st

15、acktop.x+1;b=stacktop.y;break；case 3：a=stacktop。x；b=stacktop.y-1;break； if(abab=0)find=1;if （find=1） stacktop。di=di;top+；stacktop。x=a;stacktop.y=b；stacktop.di=-1;abab=1；elseabstacktop.xstacktop.y=0；top-;coutendl；cout”走出迷宫最短的路径是：endl；cout其长度为:minlenghtendl；cout”路径是:endl；for(k=0；kminlenght;k+）cout（sstackk.x”,sstackk。x”）”；if(kminlenght-1）cout”-；if(!(（k+1）%10)coutendl；coutendl；#endif#includemmigong.hvoid main(）stack stack;int ab1010=1,1