迷宫问题的求解是一个很好的在栈或者队列等方面的应用问

迷宫问题的求解是一个很好的在栈或者队列等方面的应用问题，本次设计是利用栈的方法来实现的。问题的求解主要是随便输入一个入口坐标和出口坐标，求出一条从入口到出口的路径，如果不存在或者存在要做出相应的判断，存在时将路径用坐标的形式表现出来。#include<stdio.h>#include<stdlib.h>#defineM32#defineN32structmark//定义迷宫内点的坐标类型{intx;inty;};structElement//链栈元素{intx,y;//x行,y列intd;//d下一步的方向};typedefstructLStack//链栈{Elementelem;structLStack*next;}*PLStack;/*************栈函数****************/intInitStack(PLStack&S)//构造空栈{S=NULL;return1;}intStackEmpty(PLStackS)//判断栈是否为空{if(S==NULL)return1;elsereturn0;}intPush(PLStack&S,Elemente)//压入新数据元素{PLStackp;p=(PLStack)malloc(sizeof(LStack));p->elem=e;p->next=S;S=p;return1;}intPop(PLStack&S,Element&e)//栈顶元素出栈{PLStackp;if(!StackEmpty(S)){e=S->elem;p=S;S=S->next;free(p);return1;}elsereturn0;}/*************建立迷宫*******************/voidInitmaze(intmaze[M][N]){intm,n;//迷宫行,列inti,j;printf("请输入迷宫的行数m=");scanf("%d",&m);printf("请输入迷宫的列数n=");scanf("%d",&n);while((m<=0||m>30)||(n<=0||n>30)){printf("\n抱歉，你输入的行列数超出预设范围(0-30,0-30),请重新输入：\n\n");printf("请输入行数=：");scanf("%d",&m);printf("请输入列数=：");scanf("%d",&n);}printf("\n请输入迷宫的各行各列,用空格隔开,0代表路,1代表墙\n",m,n);for(i=1;i<=m;i++)for(j=1;j<=n;j++)scanf("%d",&maze[i][j]);printf("==========================================================\n");printf("你建立的迷宫为(最外圈为墙)路用□来表示，墙用■来表示，如下\n");printf("\n");for(i=0;i<=m+1;i++)//加一圈围墙{maze[i][0]=1;maze[i][n+1]=1;}for(j=0;j<=n+1;j++){maze[0][j]=1;maze[m+1][j]=1;}for(i=0;i<n+2;i++){printf("%d",i);//加入列坐标值 }for(i=0;i<=m+1;i++)//输出迷宫{ for(j=0;j<=n+1;j++)for(i=0;i<m+2;i++) {printf("\n"); for(j=0;j<n+2;j++) {if(maze[i][j]==0)printf("□"); if(maze[i][j]==1)printf("■"); }{maze[i][n+2]=i;printf("%d",i);//加入行坐标值}}printf("\n");printf("=======================================================\n");}}/**********************求迷宫路径函数**************************/voidMazePath(structmarkstart,structmarkend,intmaze[M][N],intdiradd[4][2]){inti,j,d;inta,b;Elementelem,e;PLStackS1,S2;InitStack(S1);InitStack(S2);if(maze[start.x][start.y]==1){printf("\n====================================================\n");printf("此迷宫无解\n");return;}maze[start.x][start.y]=2;//入口点作上标记elem.x=start.x;elem.y=start.y;elem.d=-1;//开始为-1Push(S1,elem);while(!StackEmpty(S1))//栈不为空有路径可走{Pop(S1,elem);i=elem.x;j=elem.y;d=elem.d+1;//下一个方向while(d<4)//试探上、下、左、右各个方向{a=i+diradd[d][0];b=j+diradd[d][1];if(a==end.x&&b==end.y&&maze[a][b]==0)//如果到了出口{elem.x=i;elem.y=j;Push(S1,elem);elem.x=a;elem.y=b;Push(S1,elem);while(S1)//逆置序列并输出迷宫路径序列{Pop(S1,e);Push(S2,e);}while(S2){Pop(S2,e);printf("-->(%d,%d)\n",e.x,e.y);}return;//跳出两层循环}if(maze[a][b]==0)//找到可以前进的非出口的点{maze[a][b]=2;//标记走过此点elem.x=i;elem.y=j;elem.d=d;Push(S1,elem);//当前位置入栈i=a;//下一点转化为当前点j=b;d=-1;}d++;}}printf("没有找到可以走出此迷宫的路径\n");}voidmain(){intsto[M][N];intadd[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量;{inti,cycle=0;while(cycle!=(-1)){printf("***************************************************************\n");printf("\n");printf("欢迎进入迷宫求解系统\n");printf("\n");printf("**************************************************************\n");printf("\n");printf("生成迷宫请按:1\n");printf("退出迷宫请按:2\n");printf("\n");printf("**************************************************************\n");printf("\n");printf("请选择你的操作：");scanf("%d",&i);switch(i){case1:structmarkstart,end;//start,end入口和出口的坐标Initmaze(sto);//建立迷宫printf("输入入口的横坐标,纵坐标[逗号隔开]\n");scanf("%d,%d",&start.x,&start.y);printf("输入出口的横坐标,纵坐标[逗号隔开]\n");scanf("%d,%d",&end.x,&end.y);printf("======================================================\n");printf("迷宫路径为:\n");printf("\n");MazePath(start,end,sto,add);//寻找路径printf("\n\nPress