迷宫问题-数据结构课程设计|数据结构课程设计*Name:迷宫Author:wujilinDescription:输入时候一圈都应该是# 入口为（1,1) 如果有出口 出口为(M-2,M-2)Date: 16-07-06 20:54Copyright:wujilin*/
#include
#include#define M 10 //自己规定为10*10的迷宫#define OK 1#define ERROR 0#define OVERFLOW -1#define STACK_INIT_SIZE 100#define STACKINCREMENT 10int findway(int);int NextStep(int *, int *, int );typedef struct{int x, y; //坐标int dir; //方向}ElemType;typedef struct StackNode//构造栈{ElemType *base;ElemType *top;int stacksize;}SqStack;
int InitStack(SqStack *S)//初始化栈{S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S->base){printf("memory allocation failed,goodbye");exit(1);}S->top=S->base;S->stacksize=STACK_INIT_SIZE;return OK;}int Push(SqStack *S,ElemType e)//进栈操作{if(S->top-S->base>=S->stacksize){S->base = (ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));if (!S->base){printf("memory allocation failed,goodbye");exit(1);}S->top = S->base+S->stacksize;S->stacksize += STACKINCREMENT;}*S->top++=e;return OK;}
int Pop(SqStack *S,ElemType *e)//出栈操作{if(S->top==S->base){return ERROR;}*e=*--S->top;//printf("%d\n",e);return OK;}
int StackEmpty(SqStack *S)//判断栈是否为空{if(S->top==S->base)return OK;elsereturn ERROR;}void Input(char b[M][M])//输入时候请注意把一圈都输入为墙即'#'{
int i, j;
printf("请输入迷宫形状:\n");
for (i = 0; i < M; i++){for (j = 0; j < M; j++){scanf("%c",&b[i][j]);}getchar();//吃掉内存中的残留换行符号}}
void Ouput(const char b[M][M]){int i, j;
printf("迷宫的形状为:\n");for (i = 0; i < M; i++){for (j = 0; j < M; j++){printf("%c",b[i][j]);}printf("\n");}}int FindWay(char maze[M][M]){ElemType e;int constep = 1;int x = 1, y = 1;SqStack S;
InitStack(&S);do{if (maze[x][y] == ' ')//当第3次时 maze[x][y]!=' ' 照样通不过{maze[x][y] = '1';e.x = x;e.y = y;e.dir = 1;Push(&S,e);if (x == M-2 && y == M-2){printf("存在出口\n");return 1;}NextStep(&x,&y,1);constep++;}
else{Pop(&S,&e);while (e.dir == 4 && !StackEmpty(&S)){maze[e.x][e.y] = '0';Pop(&S,&e);}
{
if (e.dir < 4){e.dir++;Push(&S,e);x = e.x;y = e.y;NextStep(&x, &y, e.dir);}else{printf("没有出口\n");return 0;}}}}while(S.top!=S.base);
return 0;}
int NextStep(int *x, int *y, int dir){
switch(dir){case 1:(*y)++;break;case 2:(*x)++;break;case 3:(*y)--;break;case 4:(*x)--;break;default:break;}return 0;}
int main(void){char a[M][M];
Input(a);Ouput(a);FindWay(a);Ouput(a);
system("pause");return 0;}
