迷宫求解最后的终结版，哎呀，这老迷宫我终于完结了！！！
话不多说，看程序吧！！！亲：
#include<iostream>
#include<stdio.h>#include<math.h>#include<string.h>#include<stdlib.h>#include<algorithm>#define LEN sizeof(struct Stack)#define INT_SIZE 1000#define INCREMENT 100using namespace std; int a[100][100]; typedef struct{ int x; int y;}Posttype;//定义结构体表明当前位置的状态
typedef struct
{ int di; //表此位置指向的方向 Posttype seat;//当前位置的坐标 int ord; //当前位置在路径中的序号}ElemType;//记录行走的路径struct Stack{ ElemType *base;//栈底指针 ElemType *top;//栈顶指针 int StackSize;//栈的尺寸}stack;//构建数据栈结构体
bool FindWay(struct Stack &S,int i,int j)//找道函数{ Posttype NextPos(Posttype a,int Dir); void PushStack(struct Stack &S,ElemType e); ElemType PopStack(struct Stack &S); Posttype curpos; ElemType e; int curstep=0; curpos.x=i; curpos.y=j; do { if(a[curpos.x][curpos.y]==-1) return true; if(a[curpos.x][curpos.y]==0||a[curpos.x][curpos.y]==2) { a[curpos.x][curpos.y]=1; e.di=1; e.ord=curstep; e.seat=curpos; PushStack(S,e); curpos=NextPos(curpos, 1); curstep++; } else { if(e.di==4&&S.base!=S.top) e=PopStack(S); if(e.di<4) { e.di++; //换下一个方向探索 curpos=NextPos(e.seat, e.di); //当前位置设为新方向的相邻块 } } }while(S.base!=S.top-1); return false;}
Posttype NextPos(Posttype a,int Dir)//寻路函数{ switch(Dir) { case 1:a.x=a.x-1;break; case 2:a.y=a.y+1;break; case 3:a.x=a.x+1;break; case 4:a.y=a.y-1;break; } return a;}
void InitStack(struct Stack &S)//栈的初始化
{ S.base=(ElemType *)malloc(INT_SIZE*sizeof(ElemType)); if(S.base==NULL) { printf("系统出现错误，请关闭后重新启动\n"); exit(0); } S.top=S.base; S.top++; S.StackSize=1000;}void PushStack(struct Stack &S,ElemType e)//元素入栈{ if(S.top-S.base>=S.StackSize) { printf("由于存储空间已经满了,系统自动增加了存储空间\n"); S.top=(ElemType *)realloc(S.base,(INT_SIZE+INCREMENT)*sizeof(ElemType)); }
*S.top=e;
S.top++;}
ElemType PopStack(struct Stack &S)//元素出栈{ ElemType e; if(S.top==S.base) exit(0); e=*(S.top-2); S.top--; return e;}
int main()//主函数{
int line,rows,i,j,starti,startj,endi,endj;
printf("欢迎使用本迷宫求解系统\n"); printf("---------------------------------------------------\n"); printf("请输入迷宫的行数和列数:\n"); cin>>line>>rows; memset(a,0,sizeof(a)); for(i=0,j=0;i<line;i++) a[i][j]=1; for(i=0,j=0;j<rows;j++) a[i][j]=1; for(i=0,j=rows-1;i<line;i++) a[i][j]=1; for(i=line-1,j=0;j<rows;j++) a[i][j]=1; printf("请输入障碍点坐标的个数:\n"); int n,m; cin>>n; m=n; while(m--) { printf("请输入第%d个障碍点的坐标:\n",n-m); cin>>i>>j; a[i][j]=1; } printf("请输入迷宫起始点的坐标:\n"); cin>>starti>>startj; a[starti][startj]=2; printf("请输入迷宫出口点的坐标:\n"); cin>>endi>>endj; a[endi][endj]=-1; struct Stack S; InitStack(S); i=starti; j=startj; if(FindWay(S,i,j)) { printf("恭喜您，我们已经找到了一条通道\n"); cout<<"("<<endi<<","<<endj<<")"<<endl; S.top--; while(S.base!=S.top) { cout<<"("<<(*S.top).seat.x<<","<<(*S.top).seat.y<<")"<<endl; PopStack(S); } } else printf("抱歉，此迷宫没有出路\n"); printf("---------------------------------------------------\n");
return 0;}