- int mg[M+2][N+2]={
- // 全局变量, 初始化数组
- {
- 1
- }
- } ;
- typedef struct{
- int i;
- int j;
- int di;
- }Box;
- typedef struct{
- Box data[MaxSize];
- int top;
- }StType;
- void InitStack(StType *&s)// 初始化栈
- {
- s=(StType *)malloc(sizeof(StType));
- s->top=-1;
- }
- bool Push(StType *&s,Box e)// 进栈
- {
- if(s->top==MaxSize-1)
- return false;
- s->top++;
- s->data[s->top]=e;
- return true;
- }
- bool StackEmpty(StType *s)// 判空
- {
- return (s->top==-1);
- }
- bool GetTop(StType *&s,Box &e)// 取栈顶元素
- {
- if(s->top==-1)
- return false;
- e=s->data[s->top];
- return true;
- }
- bool Pop(StType *&s,Box &e)// 出栈
- {
- if(s->top==-1)
- return false;
- e=s->data[s->top];
- s->top--;
- return true;
- }
- void DestroyStack(StType *&s)// 销毁栈
- {
- free(s);
- }
- bool mgpath(int xi,int yi,int xe,int ye){
- // 求解路径为(xi,yi)->(xe,ye)
- Box path[MaxSize],e;
- int i,j,di,i1,j1,k;
- bool find;
- StType *st; // 定义栈 st
- InitStack(st); // 初始化栈顶指针
- e.i=xi;e.j=yi;e.di=-1; // 设置 e 为入口
- Push(st,e); // 方块 e 进栈
- mg[xi][yi]=-1; // 将入口的迷宫值置为 - 1, 避免重复走到该方块
- while(!StackEmpty(st)) // 栈时循环
- {
- GetTop(st,e); // 取栈顶方块 e
- i=e.i;j=e.j;di=e.di;
- if(i==xe&&j==ye){
- // 找到了出口, 输出该路径
- printf("一条迷宫路径如下:\n");
- k=0;
- while(!StackEmpty(st)){
- Pop(st,e); // 出栈方块 e
- path[k++]=e; // 将 e 添加到 path 数组中
- }
- while(k>=1){
- k--;
- if(path[k].i-path[k+1].i==1){
- // 打印方向
- printf("(↓)");
- }
- if(path[k].i-path[k+1].i==-1){
- printf("(↑)");
- }
- if(path[k].j-path[k+1].j==1){
- printf("(→)");
- }
- if(path[k].j-path[k+1].j==-1){
- printf("(←)");
- }
- printf("\t(%d,%d)",path[k].i,path[k].j);
- if((k+2)%5==0) // 每输出 5 个方块后换一行
- printf("\n");
- }
- printf("\n");
- DestroyStack(st); // 销毁栈
- return true; // 输出一条迷宫路径后返回 true
- }
- find=false;
- while(di<4 && !find){
- // 找方块 (i,j) 的下一个相邻可走方块(i1,j1)
- di++;
- switch(di){
- case 0:i1=i-1;j1=j;break;
- case 1:i1=i;j1=j+1;break;
- case 2:i1=i+1;j1=j;break;
- case 3:i1=i;j1=j-1;break;
- }
- if(mg[i1][j1]==0) // 找到一个相邻可走方块, 设置 find 为真
- find=true;
- }
- if(find)// 找到了一个相邻可走方块(i1,j1)
- {
- st->data[st->top].di=di;// 修改原栈顶元素的 di 值
- e.i=i1;e.j=j1;e.di=-1;
- Push(st,e);// 相邻可走方块 e 进栈
- mg[i1][j1]=-1;// 将 (i1,j1) 进迷宫值置为 - 1, 避免重复走到该方块
- }
- else// 没有路径可走则退栈
- {
- Pop(st,e);// 将栈顶方块退栈
- mg[e,i][e,j]=0;// 让退栈方块的位置变为其他路径可走方块
- }
- }
- DestroyStack(st);// 摧毁栈
- return false;// 表示没有走路径, 返回 false
- }
- void print(){
- // 打印迷宫的布置 地图
- int i,j;
- for(i=0;i<M+2;i++){
- for(j=0;j<N+2;j++){
- if(mg[i][j]==1)
- printf("█");
- else
- printf(" ");
- }
- printf("\n");
- }
- }
- void putin(){
- int i,j,k=30;//k 表示障碍物的个数
- srand((int)time(0));// 随机函数
- for(i=0;i<M+2;i++){
- for(j=0;j<N+2;j++){
- if(i==0||i==M+1||j==0||j==N+1)// 设置边框
- mg[i][j]=1;
- }
- }
- for(i=0;i<k;i++){
- // 随机位置生成障碍物
- mg[random(10)][random(10)]=1;
- }
- mg[1][1]=0;// 起点与终点不能为障碍物
- mg[9][9]=0;
- }
- void set(){
- // 过渡
- putin();
- print();
- if(!mgpath(1,1,M,N))
- printf("该迷宫为题没有解!\n");
- }
- void aa(){
- int n;
- printf("打印迷宫请按 1, 退出请按 0\n");
- scanf("%d",&n);
- if(n){
- system("cls");
- memset(mg,0,sizeof(mg));// 把 mg 数组清零
- set();
- aa();
- }else return;// 返回主函数
- }
- int main(){
- aa();
- return 1;
- }
来源: http://www.bubuko.com/infodetail-3343747.html