迷宫问题的C-C++算法实现

基于栈的C语言迷宫问题与实现一．问题描述多年以来，迷宫问题一直是令人感兴趣的题目。实验心理学家训练老鼠在迷宫中寻找食物。许多神秘主义小说家也曾经把英国乡村花园迷宫作为谋杀现场。于是，老鼠过迷宫问题就此产生，这是一个很有趣的计算机问题，主要利用“栈”是老鼠通过尝试的办法从入口穿过迷宫走到出口。迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的路径。一个迷宫可用上图所示方阵[m,n]表示，0表示能通过，1表示不能通过。现假设耗子从左上角[1,1]进入迷宫，编写算法，寻求一条从右下角[m,n]出去的路径。下图是一个迷宫的示意图：二．算法基本思想迷宫求解问题是栈的一个典型应用。基本算法思想是：在某个点上，按照一定的顺序（在本程序中顺序为上、右、下、左）对周围的墙、路进行判断（在本程序中分别用1、0）代替，若周围某个位置为0，则移动到该点上，再进行下一次判断；若周围的位置都为1（即没有通路），则一步步原路返回并判断有无其他通路，然后再次进行相同的判断，直到走到终点为止，或者确认没有任何通路后终止程序。要实现上述算法，需要用到栈的思想。栈里面压的是走过的路径，若遇到死路，则将该位置（在栈的顶层）弹出，再进行下一次判断；若遇到通路，则将该位置压栈并进行下一次判断。如此反复循环，直到程序结束。此时，若迷宫有通路，则栈中存储的是迷宫通路坐标的倒序排列，再把所有坐标顺序打印后，即可得到正确的迷宫通路。三．程序具体部分的说明1.迷宫的生成根据题目的要求，迷宫的大小是自定义输入的。所以在程序中用malloc申请动态二维数组。数组中的元素为随机生成的0、1。数组周围一圈的元素全部定义为1，以表示边界。2.栈的C语言实现为了实现栈的功能，即清空、压栈、弹出、返回栈顶元素，在程序中编写了相应的函数。MakeNULL清空栈Push将横、纵坐标压栈Topx返回栈顶存储的横坐标Topy返回栈顶存储的纵坐标Pop弹出栈顶元素3.具体的判断算法当位置坐标（程序中为XY）移到某一位置时，将这个位置的值赋值为1并压栈，以说明该点已经走过。接着依次判断该点的上、右、下、左是否为0，若有一方为0，则移动到该位置上，进行下次判断；若为周围位置全部是1，则将该点压栈后不断弹出，每次弹出时判断栈顶元素（即走过的路）周围有无其他通路。如果有的话，则选择该方向继续走下去；如果栈已经为空仍然没有找到出路，则迷宫没有出口程序结束。当XY走到出口坐标时，程序判断部分结束。栈里面存储的是每个走过的点的坐标，将这些横纵坐标分别存储在两个数组中，最后将数组中的坐标元素倒序输出，即得到了完整的路径。四．程序源代码及注释//Maze.cpp:定义控制台应用程序的入口点。//#includestdafx.h#includestdio.h#includestring.h#includemalloc.h#includestdlib.h#includetime.htypedefintElementtype;structnode{Elementtypeval1;Elementtypeval2;node*next;};//定义结构体typedefnode*MAZE;voidMakeNull(MAZE&S);voidPush(Elementtypex,Elementtypey,MAZES);voidPop(MAZES);ElementtypeTopx(MAZES);ElementtypeTopy(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\n);scanf(%d%d,&l,&w);getchar();n1=w+2;n2=l+2;//为迷宫加上边界max=n1*n2;p=(int**)malloc(n1*sizeof(int));for(i=0;in1;i++)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;imax;i++){x1[i]=0;}for(i=0;imax;i++){y1[i]=0;}//先将存储路径的数组元素全赋值为0for(i=0;in1;i++){for(j=0;jn2;j++){if(i==0||j==0){p[i][j]=1;}elseif(i==n1-1||j==n2-1){p[i][j]=1;}elsep[i][j]=rand()%2+0;}}//生成二维10随机数组p[1][1]=0;p[n1-2][n2-2]=0;//定义迷宫的入口及出口printf(生成的迷宫如下（代表墙0代表路）：\n);for(i=0;in1;i++){{for(j=0;jn2;j++)printf(%2d,p[i][j]);}printf(\n);}//打印迷宫MAZES;MakeNull(S);//清空栈i=1;j=1;if(p[1][2]==1&&p[2][1]==1){printf(Thereisnowayout);agetchar();return0;}//判断入口是否就是死路else{do{if(p[i-1][j]==0){x=i;y=j;Push(x,y,S);p[i][j]=1;i=i-1;}//判断能否向上走elseif(p[i-1][j]==1&&p[i][j+1]==0){x=i;y=j;Push(x,y,S);p[i][j]=1;j=j+1;}//判断能否向右走elseif(p[i-1][j]==1&&p[i][j+1]==1&&p[i+1][j]==0){x=i;y=j;Push(x,y,S);k=Topx(S);p[i][j]=1;i=i+1;}//判断能否向下走elseif(p[i-1][j]==1&&p[i][j+1]==1&&p[i+1][j]==1&&p[i][j-1]==0){x=i;y=j;Push(x,y,S);p[i][j]=1;j=j-1;}//判断能否向左走elseif(p[i-1][j]==1&&p[i][j+1]==1&&p[i+1][j]==1&&p[i][j-1]==1)//判断如果为死路{p[i][j]=1;x=i;y=j;Push(x,y,S);for(;;){Pop(S);//弹出栈顶元素x=Topx(S);y=Topy(S);//返回栈顶元素横纵坐标if(p[x-1][y]==0){i=x-1;j=y;p[i][j]=1;x=i;y=j;Push(x,y,S);break;}elseif(p[x-1][y]==1&&p[x][y+1]==0){i=x;j=y+1;p[i][j]=1;x=i;y=j;Push(x,y,S);break;}elseif(p[x-1][y]==1&&p[x][y+1]==1&&p[x+1][y]==0){i=x+1;j=y;p[i][j]=1;x=i;y=j;Push(x,y,S);break;}elseif(p[x-1][y]==1&&p[x][y+1]==1&&p[x+1][y]==1&&p[x][y-1]==0){i=x;j=y-1;p[i][j]=1;x=i;y=j;Push(x,y,S);break;}//判断弹出后栈顶元素周围有无通路elseif(x==1&&y==1){printf(Thereisnowayout);getchar();return0;}//如果栈顶元素为入口则迷宫无出路}}}while(i!=n1-2||j!=n2-2);//循环截止条件}printf(Success!\nTherouteis:\n);for(i=0;;i++){a=Topx(S);b=Topy(S);Pop(S);x1[i]=a;y1[i]=b;//将栈顶元素坐标存储在数组中if(a==1&&b==1){getchar();break;}}for(i=max-1;i=0;){if(x1[i]!=0&&(x1[i]!=x1[i-1]||y1[i]!=y1[i-1])){printf(%d,%d,x1[i],y1[i]);i--;}elseif(x1[i]!=0&&(x1[i]==x1[i-1]&&y1[i]==y1[i-1])){printf(%d,%d,x1[i],y1[i]);i=i-2;}elsei--;}//倒序打印数组得到顺序出路坐标printf(%d,%d,n1-2,n2-2);//打印出口坐标getchar();return0;}voidMakeNull(MAZE&S)//清空栈的函数{S=newnode;S-next=NULL;}voidPush(Elementtypex,Elementtypey,MAZES)//压栈函数{MAZEstk;stk=newnode;stk-val1=x;stk-val2=y;stk-next=S-next;S-next=stk;}voidPop(MAZES)//弹出函数{MAZEstk;if(S-next){stk=S-next;S-next=stk-next;deletestk;}}ElementtypeTopx(MAZES)//返回横坐标函数{if(S-next)return(S-next-val1);elsereturnNULL;}ElementtypeTopy(MAZES)//返回纵坐标函数{if(S-next)return(S-next-val2);elsereturnNULL;}另一种方法实现的迷宫代码#ifndefMMIGONG_H#defineMMIGONG_H#defineMAX_SIZE100#includeiostreamusingnamespacestd;structNode{intx;inty;intdi;};classStack{private:intrrow;intccolm;inttop;intcount;intminlenght;Nodestack[MAX_SIZE];Nodesstack[MAX_SIZE];public:Stack();//初始化//int**InsortMiGong();//输入迷宫(即一个二维数组)voidFindPath(intab[][10]);//找出迷宫的出路};Stack::Stack()//初始化{rrow=0;ccolm=0;top=-1;count=1;minlenght=MAX_SIZE;}/*int**Stack::InsortMiGong()//输入迷宫(即一个二维数组){introw=1,colm=1;while(true){cout请输入迷宫的行数和列数:;cinrowcolm;if(row=0||colm=0){cout输入错误!请重新输入:endl;rrow=row;ccolm=colm;continue;}else{rrow=row;ccolm=colm;break;}}int*mg[];cout请输入迷宫矩阵(只有0和1两个数构成):;for(inti=0;irow;i++)for(intj=0;jcolm;j++)cinmg[i][j];returnmg;}*/voidStack::FindPath(intab[][10])//找出迷宫的出路{inta,b,di,find,k