C语言迷宫问题递归和非递归求解

#include<stdio.h> #include<iostream> #include<stdlib.h> #define MAXSIZE 50 using namespace std; typedef struct{ int x,y; }pot; int choices[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//方向数组 int flag=0; void msgbox() { printf("-------------------------------------------\n"); printf("-------------迷宫非递归编程游戏------------\n"); printf("- -\n"); printf("- 制作者：徐奕 学号：E21614061 -\n"); printf("- -\n"); if(flag==0) { printf("-------------------------------------------\n"); system("pause"); flag=1; } else { printf("- 注意：迷宫最外层不计数 -\n"); printf("- -\n"); printf("- 基本操作： -\n"); printf("- 开始游戏-->S 退出游戏-->E -\n"); printf("- -\n"); printf("-------------------------------------------\n"); } } void cur_sys() { system("pause"); system("cls"); } class point{ private: int x,y; int d; public: pot start,ending; void MazePath(pot start,pot ending,int maze[MAXSIZE][MAXSIZE],int m,int n); //迷宫解的路径 void initmaze(int maze[MAXSIZE][MAXSIZE],int m,int n); //初始化迷宫路径，随机生成 void rewrite(int maze[MAXSIZE][MAXSIZE],int m,int n); //随机生成的迷宫可能没有通路，利用此函数修改迷宫 }; typedef struct LStackNode { point elem; struct LStackNode *next; }LStack,*Stack; Stack InitStack(Stack S) { S=NULL; return S; } int StackEmpty(Stack S) { if(S==NULL) return 1; else return 0; } Stack Push(Stack S,point e) { Stack P; P=(Stack)malloc(sizeof(LStack)); P->elem=e; P->next=S; S=P; return S; } Stack DelTop(Stack S) //删除栈头 { Stack P; P=S; if(!StackEmpty(S)) { S=S->next; free(P); return S; } } point Pop(Stack S,point e) //返回栈顶 { if(!StackEmpty(S)) { e=S->elem; return e; } } void point::MazePath(pot start,pot ending,int maze[MAXSIZE][MAXSIZE],int m,int n) { int i,j,d; int a,b; point elem,e; Stack S1,S2; S1=InitStack(S1); S2=InitStack(S2); maze[start.x][start.y]=2; //修改入口坐标，做标记 elem.x=start.x; elem.y=start.y; elem.d=0; //开始为0 S1=Push(S1,elem); while(!StackEmpty(S1)) { elem=Pop(S1,elem); S1=DelTop(S1); i=elem.x; j=elem.y; d=elem.d+1; while(d<=4) { a=i+choices[d-1][0]; b=j+choices[d-1][1]; if(a==ending.x&&b==ending.y&&maze[a][b]==0) //出口 { elem.x=i; elem.y=j; elem.d=d; S1=Push(S1,elem); elem.x=a; elem.y=b; elem.d=0; //方向输出为0，判断是否为出口 S1=Push(S1,elem); printf("\n-----------------------------\n\n路径为:(行坐标，列坐标，方向)\n"); while(S1) //逆置序列 并输出路径 { e=Pop(S1,e); S1=DelTop(S1); S2=Push(S2,e); } while(S2) { e=Pop(S2,e); S2=DelTop(S2); if(e.d==1) printf("-->(%d,%d,右)",e.x,e.y); else if(e.d==2) printf("-->(%d,%d,下)",e.x,e.y); else if(e.d==3) printf("-->(%d,%d,左)",e.x,e.y); else if(e.d==4) printf("-->(%d,%d,上)",e.x,e.y); else printf("-->(%d,%d,出口)",e.x,e.y); maze[e.x][e.y]=3; } printf("\n\n"); for(i=0;i<=m+1;i++){ for(j=0;j<=n+1;j++) if(maze[i][j]==3) printf("0 "); else printf("1 "); printf("\n"); } return; }//if if(maze[a][b]==0) { maze[a][b]=2; elem.x=i; elem.y=j; elem.d=d; S1=Push(S1,elem); i=a; j=b; d=0; } d++; } } printf("没有出迷宫的路径\n"); } void point::initmaze(int maze[MAXSIZE][MAXSIZE],int m,int n) { int i,j; for(i=1;i<=m;i++) for(j=1;j<=n;j++) maze[i][j]=rand()%2; for(i=0;i<=m+1;i++) { maze[i][0]=maze[i][n+1]='*'; } for(j=0;j<=n+1;j++) { maze[0][j]=maze[m+1][j]='*'; } printf("输出迷宫:\n"); for(i=0;i<=m+1;i++) { for(j=0;j<=n+1;j++) { if((j==0||i==0)||(j==n+1||i==m+1)) printf("%c ",maze[i][j]); else printf("%d ",maze[i][j]); } printf("\n"); } } void point::rewrite(int maze[MAXSIZE][MAXSIZE],int m,int n) { char a;int i,j; printf("是否修改某点为0(Y/N)? "); while((cin>>a)&&a!='N') { printf("输入坐标空格分隔："); int a,b; scanf("%d %d",&a,&b); maze[a][b]=0; system("cls");msgbox(); printf("此刻迷宫:\n"); for(i=0;i<=m+1;i++) { for(j=0;j<=n+1;j++) { if((j==0||i==0)||(j==n+1||i==m+1)) printf("%c ",maze[i][j]); else printf("%d ",maze[i][j]); } printf("\n"); } printf("是否继续修改(Y/N)?\n"); } } int main() { int maze[MAXSIZE][MAXSIZE]; point Maze; msgbox(); int m,n; //迷宫行列 system("cls"); msgbox(); char x; printf("输入操作\n-"); while(cin>>x) { switch(x) { case 'S':cur_sys();msgbox(); printf("输入迷宫的行数m和列数n(空格键区分)\n"); scanf("%d%d",&m,&n); Maze.initmaze(maze,m,n); Maze.rewrite(maze,m,n); printf("输入入口坐标和出口坐标(格式X1 Y1 X2 Y2回车)\n"); scanf("%d %d %d %d",&Maze.start.x,&Maze.start.y,&Maze.ending.x,&Maze.ending.y); Maze.MazePath(Maze.start,Maze.ending,maze,m,n); cur_sys();msgbox();printf("输入操作\n-"); break; case 'E':exit(0); default:cur_sys();msgbox();printf("输入操作\n-");continue; } } }