数据结构迷宫，求解一条通路

011101110 101011110 010000010 011101110 100110000 011001100 #include <stdio.h> #include<iostream.h> #include <stdlib.h> #include <string.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; #include "base.h" #define INIT_SIZE 100 //存储空间初始分配量 #define INCREMENT 10 //存储空间分配增量 typedef struct{ //迷宫中r行c列的位置 int r; int c; }PostType; typedef struct{ int ord; //当前位置在路径上的序号 PostType seat;//当前坐标 int di; //往下一坐标的方向 }SElemType; //栈元素类型 typedef struct{ SElemType* base;//栈基址,构造前销毁后为空 SElemType* top;//栈顶 int stackSize; //栈容量 }Stack; //栈类型 Status InitStack(Stack &S){ //构造空栈s S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType)); if(!S.base) exit(OVERFLOW);//存储分配失败 S.top=S.base; S.stackSize=INIT_SIZE; return OK; }//InitStack Status StackEmpty(Stack S){ //若s为空返回TRUE,否则返回FALSE if(S.top==S.base) return TRUE; return FALSE; }//StackEmpty Status Push(Stack &S,SElemType e){ //插入元素e为新的栈顶元素 if(S.top-S.base >=S.stackSize){//栈满，加空间 S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); //存储分配失败 S.top=S.base+S.stackSize; S.stackSize+=INCREMENT; } *S.top++=e; return OK; }//push Status Pop(Stack &S,SElemType &e){//若栈不空删除栈//顶元素用e返回并返回OK，否则返回ERROR if(S.top==S.base) return ERROR; e=*--S.top; return OK; }//Pop Status DestroyStack(Stack &S){//销毁栈S, free(S.base); S.top=S.base; return OK; }//DestroyStack #include "stack.h" #define MAXLEN 10//迷宫包括外墙最大行列数目 typedef struct{ int r; int c; char adr[MAXLEN][MAXLEN];//可取' ''*' '@' '#' }MazeType; //迷宫类型 Status InitMaze(MazeType &maze){ //初始化迷宫若成功返回TRUE,否则返回FALSE int i,j; int s[MAXLEN][MAXLEN]; cout<<"输入迷宫的行和列: "<<endl; cin>>maze.r>>maze.c; //迷宫行和列数 for(i=0;i<=maze.c+1;i++){//迷宫行外墙 maze.adr[0][i]='#'; maze.adr[maze.r+1][i]='#'; }//for for( i=0;i<=maze.r+1;i++){//迷宫列外墙i maze.adr[i][0]='#'; maze.adr[i][maze.c+1]='#'; } cout<<"按行输入迷宫的值:"<<endl; for(i=1;i<=maze.r;i++){ for(int p=1;p<=maze.c;p++) cin>>s[i][p]; } for( i=1;i<=maze.r;i++){ for(j=1;j<=maze.c;j++) { if(s[i][j]==0) maze.adr[i][j]=' ';//初始化迷宫 else maze.adr[i][j]='#';//迷宫障碍用'#'标记 } } return OK; }//InitMaze Status Pass(MazeType maze,PostType curpos){ //当前位置可通则返回TURE,否则返回FALSE if(maze.adr[curpos.r][curpos.c]==' ')//可通 return TRUE; else return FALSE; }//Pass Status FootPrint(MazeType &maze,PostType curpos){ //若走过并且可通返回TRUE,否则返回FALSE //在返回之前销毁栈S maze.adr[curpos.r][curpos.c]='*';//"*"表示可通 return OK; }//FootPrint PostType NextPos(PostType &curpos,int i){ //指示并返回下一位置的坐标 PostType cpos; cpos=curpos; switch(i){ //1.2.3.4分别表示东,南,西,北方向 case 1 : cpos.c+=1; break; case 2 : cpos.r+=1; break; case 3 : cpos.c-=1; break; case 4 : cpos.r-=1; break; case 8: { cpos.r-=1; cpos.c+=1; break; } case 5:{ cpos.r+=1; cpos.c+=1; break; } case 6:{ cpos.r+=1; cpos.c-=1; break; } case 7:{ cpos.r-=1; cpos.c-=1; break; } default: exit(ERROR); } return cpos; }//Nextpos Status MarkPrint(MazeType &maze,PostType curpos){ //曾走过但不是通路标记并返回OK maze.adr[curpos.r][curpos.c]='@';//"@"表示曾走过但不通 return OK; }//MarkPrint Status MazePath(MazeType &maze,PostType start,PostType end){ //若迷宫maze存在从入口start到end的通道则求得一条存放在栈中 //并返回TRUE,否则返回FALSE Stack S; PostType curpos; int curstep;//当前序号,1.2.3.4分别表示东,南,西,北方向 SElemType e; InitStack(S); curpos=start; //设置"当前位置"为"入口位置" curstep=1; //探索第一步 do{ if(Pass(maze,curpos)){//当前位置可以通过, //即是未曾走到过的通道 FootPrint(maze,curpos);//留下足迹 e.ord=curstep; e.seat=curpos; e.di=1; Push(S,e); //加入路径 if(curpos.r==end.r&& curpos.c==end.c) if(!DestroyStack(S))//销毁失败 exit(OVERFLOW); else return TRUE; //到达出口 else{ curpos=NextPos(curpos,1); //下一位置是当前位置的东邻 curstep++; //探索下一步 }//else }//if else{ //当前位置不通 if(!StackEmpty(S)){ Pop(S,e); while(e.di==8 && !StackEmpty(S)){ MarkPrint(maze,e.seat); Pop(S,e); //留下不能通过的标记,并退一步 }//while if(e.di < 8){ e.di++;//换下一个方向探索 Push(S,e); curpos=NextPos(e.seat,e.di);//设定当前位置是该 //新方向上的相邻 }//if }//if }//else }while(!StackEmpty(S)); if(!DestroyStack(S))//销毁失败 exit(OVERFLOW); else return FALSE; }//MazePath void PrintMaze(MazeType &maze){ //将标记路径信息的迷宫输出到终端(包括外墙) int i,j; printf("\nShow maze path(*---pathway):\n\n"); printf(" "); for(i=0;i<=maze.c+1;i++)//打印列数名 printf("%4d",i); printf("\n\n"); for(i=0;i<=maze.r+1;i++){ printf("%2d",i);//打印行名 for(j=0;j<=maze.c+1;j++) printf("%4c",maze.adr[i][j]);//输出迷宫//当前位置的标记 printf("\n\n"); } }//PrintMaze void main(){ //主函数 MazeType maze; PostType start,end; char cmd; do{ printf("-------迷宫--------\n"); if(!InitMaze(maze)){ //初始化并创建迷宫 printf("\nInitialization errors!!!\n"); exit(OVERFLOW);