迷宫求解

definition.h ======================================================== #define INIT_SIZE 100 //存储空间初始分配量 #define INCREMENT 10 //存储空间分配增量

typedef struct{ unsigned ord, x, y; //通道块在路径上的“序号”，通道快在迷宫中的“坐标位置” short di; //从此通道块走向下一通道块的“方向” }ElemType;

typedef struct{ ElemType *top, *base; //栈顶指针和栈底指针 unsigned stacksize; //当前已分配的存储空间，以元素为单位 }SqStack;

int InitStack(SqStack *);//创建一个空栈 int Push(SqStack *, ElemType);//插入栈顶 ElemType Pop(SqStack *); //删除栈顶元素 void NextPos(unsigned *, unsigned *, short);//定位下一个位置 ====================================================================

function.c =============================================================== #include<stdio.h> #include<malloc.h> #include"definition.h"

int InitStack(SqStack *S) //创建一个空栈 { S->base=(ElemType *)malloc( INIT_SIZE * sizeof(ElemType) ); if(!S->base) //空间分配失败 return 1; //空间分配成功 S->top=S->base;//置栈顶指针 S->stacksize=INIT_SIZE;//栈大小 return 0; }

int Push(SqStack *S, ElemType e) //插入栈顶 { if( (unsigned)(S->top - S->base) >= S->stacksize){//栈满，追加存储空间 S->base=(ElemType *)realloc(S->base, (S->stacksize+INCREMENT)*sizeof

(ElemType) ); if(!S->base)//分配失败，返回1 return 1; //分配成功 S->top = S->base + S->stacksize;//置栈顶指针 S->stacksize += INCREMENT;//栈大小 }

*S->top++ = e;//接收输入后，S->top指向栈顶元素的下一个位置

return 0; }

ElemType Pop(SqStack *S) //删除栈顶元素 { if(S->base == S->top){//空栈，返回0 S->base->di=0; return *S->base; } return *( --(S->top) );//不空，栈顶指针下移（即删除栈顶元素），并且返回栈顶元素 }

void NextPos(unsigned *x, unsigned *y, short di)//定位下一个位置 { switch(di){ case 1: ++(*x); break; case 2: ++(*y); break; case 3: --(*x); break; case 4: --(*y); break; default: break; } } ==============================================================================

main.c =============================================== #include<stdio.h> #include<malloc.h> #include"definition.h"

int main() { SqStack S; unsigned x, y, curstep;//迷宫坐标，探索步数 ElemType e; char maze[10][10]={ {'#',' ','#','#','#','#','#','#','#','#'}, {'#',' ',' ','#',' ',' ',' ','#',' ','#'}, {'#',' ',' ','#',' ',' ',' ','#',' ','#'}, {'#',' ',' ',' ',' ','#','#',' ',' ','#'}, {'#',' ','#','#','#',' ',' ',' ',' ','#'}, {'#',' ',' ',' ','#',' ',' ',' ',' ','#'}, {'#',' ','#',' ',' ',' ','#',' ',' ','#'}, {'#',' ','#','#','#',' ','#','#',' ','#'}, {'#','#',' ',' ',' ',' ',' ',' ',' ','#'}, {'#','#','#','#','#','#','#','#',' ','#'}, };

printf("迷宫：\n"); for(x=0; x<10; x++){ for(y=0; y<10; y++) printf("%c", maze[x][y]); printf("\n"); }

if( InitStack(&S) ){ printf("创建堆栈失败。\n"); return 1; }

//入口坐标 x=1; y=0; curstep=1;//探索第一步 //进入迷宫 do{ if(maze[y][x]==' '){//如果当前位置可以通过 maze[y][x]='1';//留下足迹 e.x=x; e.y=y; e.di=1; e.ord=curstep; Push(&S, e);//加入路径，即压栈 if(x==8 && y==9)//到达终点 break; NextPos(&x, &y, 1);//下一位置是当前位置的东邻 curstep++; } else{//如果当前位置不能通过 if(S.top != S.base){ e=Pop(&S); while(e.di==4 && S.top!=S.base){ maze[e.y][e.x]='0';//留下不能通过足迹 e=Pop(&S);//退回一步，即出栈 } if(e.di<4){ e.di++; Push(&S, e); //重置坐标 x=e.x; y=e.y; NextPos(&x, &y, e.di);//寻找下一位置 } } } }while(S.top != S.base);

printf("\n路线：\n"); for(x=0; x<10; x++){ for(y=0; y<10; y++) printf("%c", maze[x][y]); printf("\n"); }

free(S.base);

return 0; }