资源描述:
《迷宫问题的C-C--算法实现汇总.doc》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、基于栈的C语言迷宫问题与实现一.问题描述多年以来,迷宫问题一直是令人感兴趣的题目。实验心理学家训练老鼠在迷宫中寻找食物。许多神秘主义小说家也曾经把英国乡村花园迷宫作为谋杀现场。于是,老鼠过迷宫问题就此产生,这是一个很有趣的计算机问题,主要利用“栈”是老鼠通过尝试的办法从入口穿过迷宫走到出口。迷宫只有两个门,一个叫做入口,另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁,对前进方向形成了多处障碍,在迷宫的唯一出口处放置了一块奶酪,吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫
2、问题,即找出从入口到出口的路径。一个迷宫可用上图所示方阵[m,n]表示,0表示能通过,1表示不能通过。现假设耗子从左上角[1,1]进入迷宫,编写算法,寻求一条从右下角[m,n]出去的路径。下图是一个迷宫的示意图:二.算法基本思想迷宫求解问题是栈的一个典型应用。基本算法思想是:在某个点上,按照一定的顺序(在本程序中顺序为上、右、下、左)对周围的墙、路进行判断(在本程序中分别用1、0)代替,若周围某个位置为0,则移动到该点上,再进行下一次判断;若周围的位置都为1(即没有通路),则一步步原路返回并判断有无其他通
3、路,然后再次进行相同的判断,直到走到终点为止,或者确认没有任何通路后终止程序。要实现上述算法,需要用到栈的思想。栈里面压的是走过的路径,若遇到死路,则将该位置(在栈的顶层)弹出,再进行下一次判断;若遇到通路,则将该位置压栈并进行下一次判断。如此反复循环,直到程序结束。此时,若迷宫有通路,则栈中存储的是迷宫通路坐标的倒序排列,再把所有坐标顺序打印后,即可得到正确的迷宫通路。三.程序具体部分的说明1.迷宫的生成根据题目的要求,迷宫的大小是自定义输入的。所以在程序中用malloc申请动态二维数组。数组中的元素为
4、随机生成的0、1。数组周围一圈的元素全部定义为1,以表示边界。2.栈的C语言实现为了实现栈的功能,即清空、压栈、弹出、返回栈顶元素,在程序中编写了相应的函数。MakeNULL清空栈Push将横、纵坐标压栈Topx返回栈顶存储的横坐标Topy返回栈顶存储的纵坐标Pop弹出栈顶元素3.具体的判断算法当位置坐标(程序中为XY)移到某一位置时,将这个位置的值赋值为1并压栈,以说明该点已经走过。接着依次判断该点的上、右、下、左是否为0,若有一方为0,则移动到该位置上,进行下次判断;若为周围位置全部是1,则将该点压栈
5、后不断弹出,每次弹出时判断栈顶元素(即走过的路)周围有无其他通路。如果有的话,则选择该方向继续走下去;如果栈已经为空仍然没有找到出路,则迷宫没有出口程序结束。当XY走到出口坐标时,程序判断部分结束。栈里面存储的是每个走过的点的坐标,将这些横纵坐标分别存储在两个数组中,最后将数组中的坐标元素倒序输出,即得到了完整的路径。一.程序源代码及注释//Maze.cpp:定义控制台应用程序的入口点。//#include"stdafx.h"#include#include#incl
6、ude#include#includetypedefintElementtype;structnode{Elementtypeval1;Elementtypeval2;node*next;};//定义结构体typedefnode*MAZE;voidMakeNull(MAZE&S);voidPush(Elementtypex,Elementtypey,MAZES);voidPop(MAZES);ElementtypeTopx(MAZES);Elemen
7、ttypeTopy(MAZES);//申明函数int_tmain(intargc,_TCHAR*argv[]){int**p,*q,*x1,*y1,i,j,k,n1,n2,m1,m2,l,w,max;intx,y;inta,b,c,d;printf("输入迷宫长度及宽度l和w");scanf("%d%d",&l,&w);getchar();n1=w+2;n2=l+2;//为迷宫加上边界max=n1*n2;p=(int**)malloc(n1*sizeof(int));for(i=0;i8、p[i]=(int*)malloc(n2*sizeof(int));//生成二维动态数组srand(time(NULL));x1=(int*)malloc(max*sizeof(int));//生成动态数组用于存储路径y1=(int*)malloc(max*sizeof(int));//生成动态数组用于存储路径for(i=0;i