《走迷宫(C语言).docx》由会员分享,可在线阅读,更多相关《走迷宫(C语言).docx(5页珍藏版)》请在金锄头文库上搜索。
1、迷宫问题【问题描述】 以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。 【基本要求】首先实现一个以链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出,其中(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向。如:对于下列教据的迷宫,输出的一条通路为:(1,1,1 ),(l , 2,2),(2,2,2),(3 ,2,3),(3 ,l, 2),。【测试数据】迷宫的测试数据如下:左上角(l,l)为入口右下角(8, 9)为出口。【实现提示】 计算机解迷
2、宫通常用的是“穷举求解”方法,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路。假如所有可能的通路都探索到而未能到达出口,则所设定的迷宫没有通路。可以二维数组存储迷宫数据,通常设定入口点的下标为(1,1),出口点的下标为(n,n)。为处理方便起见,可在迷宫的四周加一圈障碍。对于迷宫中任一位置,均可约定有东、南、西、北(编号分别为1,2,3,4)四个方向可通。 #include #include #define stackinitsize 200#define stackincrement 10typedef stru
3、ct int x; int y;locat;typedef struct locat seat; int direct;SET;typedef struct SET *base; SET *top; int stacksize;stack;int mg1110;void initstack(stack &s) s.base=(SET *)malloc(stackinitsize*sizeof(SET); if(!s.base) exit(0); s.top=s.base; s.stacksize=stackinitsize;int empty(stack s) if(s.base=s.top)
4、 return 1; else return 0;int pass(locat e) if(mge.xe.y=0) return 1; else return 0;void printpass(locat e) mge.xe.y=7;void push(stack &s,SET e) if(s.top-s.base=s.stacksize) s.base=(SET *)realloc(s.base,(stackinitsize+stackincrement)*sizeof(SET); if(!s.base) exit(0); s.top=s.base+s.stacksize; s.stacks
5、ize+=stackincrement; *s.top=e; s.top+;locat next(locat e,int n) locat E; switch(n) case 2:E.x=e.x+1; E.y=e.y; break; case 1:E.x=e.x; E.y=e.y+1; break; case 4:E.x=e.x-1; E.y=e.y; break; case 3:E.x=e.x; E.y=e.y-1; break; return E;int down(stack &s,SET &e) if(s.base=s.top) return 0; else s.top-; e=*s.t
6、op; return 1; void printunpass(locat e) mge.xe.y=3;int maze() stack s; initstack(s); locat curpos,start,end; start.x=1; start.y=1; end.x=9; end.y=8; SET e; curpos=start; do if(pass(curpos) printpass(curpos); e.seat=curpos; e.direct=1; push(s,e); if(curpos.x=end.x&curpos.y=end.y) return 0; curpos=nex
7、t(e.seat,e.direct); else if(!empty(s) down(s,e); while(e.direct=4&!empty(s) printunpass(e.seat); down(s,e); if(e.direct4) e.direct+; push(s,e); curpos=next(e.seat,e.direct); while(!empty(s); printf(No Way!n); return 0;void print() int i,j; printf(*n); for(i=0;i11;i+) for(j=0;j10;j+) switch(mgij) case 0:printf( ); break; case 1:printf(); break; case 3:printf(); break; case 7:printf(O ); break; printf(n); int main() FILE *fp; if(fp=fopen(abcd.txt,r)=NULL) return 0; int i,j; for(i=0;i11;i+) for(j=0;j10;j+) fscanf(fp,%d,&mgij); maze(); print();