20113217迷宫问题源代码.docVIP

20113217迷宫问题源代码 #include stdafx.h #include stdio.h #include stdlib.h #define M 16/*宏定义*/ #define N 16 #define OVERFLOW -1 typedef struct { unsigned x,y;/*通道块在路径上的序号和在迷宫中的坐标位置*/ short di; /* 从此通道块走向下一通道块的“方向” */ }ElemType; typedef struct Node { /* 定义结点 */ ElemType data; struct Node* next; } Node,*LinkList; typedef struct { /* 定义链栈 */ LinkList top; unsigned length; /* 栈中元素个数 */ } LStack; void DestroyStack( LStack *S ); void InitStack( LStack *S ); int Pop( LStack *S ,ElemType *e ); int Push( LStack *S,ElemType e); void NextPos(int *x ,int*y,int di); void GetTop(LStack *L,ElemType e); void InitMaze(int MAZE[][N]); int _tmain(int argc, _TCHAR* argv[]) { int i=0,j=1,startx,starty,endx,endy; int x,y;/* 迷宫坐标，探索步数 */ ElemType e; LStack S,T; int maze[M][N]={0}; char dir[6]={ ,R,D,L,U}; InitStack(S); InitStack(T); InitMaze(maze); printf(形象化建立的迷宫图形，■号代表墙壁，空格代表通路：\n); for ( x = 0;x M;x++) { for ( y = 0;y N;y++ ) { if(maze[x][y]==0) printf( ); else if(maze[x][y]) printf(■); } printf(\n); } printf(请输入迷宫迷宫入口行列值，用逗号分隔，按回车结束：); scanf_s(%d,%d,startx,starty); printf(请输入迷宫的出口行列值，用逗号分隔，按回车结束：); scanf_s(%d,%d,endx,endy); x = startx; /*迷宫入口*/ y = starty; do { /* 进入迷宫找路，本程序的核心*/ if ( maze[x][y] == 0 ) { /* 如果当前位置可以通过 */ maze[x][y] = 3;/* 留下足迹 */ e.x = x; e.y = y; e.di = 1; if (!Push(S,e) ) { /* 加入路径，即压栈 */ exit(OVERFLOW); //fprintf( stderr,内存不足。\n ); } if ( x == endx y == endy ) { /* 到达终点 */ break; } NextPos(x,y,1); /* 下一位置是当前位置的右边 */ } else { /* 如果当前位置不能通过 */ if (S.length!=0) { Pop(S,e); while (e.di == 4 S.length!=0) { maze[e.x][e.y] = 4; /* 留下不能通过足迹 */ Pop(S, e); /* 退回一步，即出栈 */ } if (e.di 4) { e.di++; if (!Push(S,e) ) { /* 加入路径，即压栈 */ exit(OVERFLOW); //fprintf( stderr,内存不足。\n ); } x = e.x;/* 重置坐标 */ y = e.y;