数据结构迷宫求解

#include "my.h" #define N 10 int map[N][N]={ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1} }; int main() { int i,j; SqStack s; PosType curpos,start={1,1},end={8,8}; ElemType e; InitStack(&s); curpos = start; int curstep = 1; do { if( Pass(map,curpos) ) //当前位置可以通过，即是未曾走到过的通道块 { FootPrint(map,curpos); //给e赋值 e.ord = curstep; e.seat = curpos; e.di = 1; Push(&s,e); if(curpos.x == end.x && curpos.y == end.y) break;; curpos = NextPos( curpos, 1 ); curstep++; }//if else //当前位置不能通过 { if( ! EmptyStack(&s) ) { Pop(&s, &e); while(e.di == 4 && !EmptyStack(&s)) { FootPrint(map,e.seat); Pop(&s,&e); } if(e.di < 4) { e.di++; Push(&s,e); curpos = NextPos(e.seat, e.di); } } } }while( !EmptyStack(&s) ); //将路径输出 ElemType *ps; ps = s.base; while(ps != s.top ) //将求解的路径的值设置为2 { map[ps->seat.x][ps->seat.y] = 2; ps++; } //显示 for(i=0; i<N; i++) //2为走的路径 { for(j=0; j<N; j++) printf("%d ",map[i][j]); putchar('\n'); } return 0; }