migong.rar_C++_迷宫 C++

#include <iostream.h> #include <stdlib.h> #include<stdio.h> #include <malloc.h> const int stack_init_size = 64; //栈的初始长度 64 const int stack_add_size = 32; //栈每次增加的长度 32 //初始化迷宫元素seat[][] //seat[][]为0是不通,为1是通,为2是访问过,为三是无法走通的路线 //构建一个11X10的迷宫,为其赋值,入口在(1,1),出口在(9,8) static int seat[11][10]= { {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,1,1}, {1,0,1,1,1,0,0,1,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,1,1}, {1,0,1,1,1,1,0,0,1,1}, {1,1,1,0,0,0,1,0,1,1}, {1,1,1,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1} }; typedef struct pos{ int x; int y; bool operator==(pos &a){ if (x==a.x&&y==a.y) return true; else return false; }; }; struct stackelem{ int ord; //在路径上的序号 pos p; //坐标,即数组seat的坐标 int di; //方向 有8个 stackelem(){ }; stackelem(int a,pos b,int c){ ord = a; p = b; di = c; }; }; //一个顺序栈的结构,有两个指针(前面定义的stackelem类型)和栈的大小size struct Stack{ stackelem *top; stackelem *base; int size; }Stack; //定义一个指针类型*sqstack; typedef struct Stack *Sqstack; void init_stack(Sqstack &S){ //初始化一个栈. S=(Sqstack)malloc(sizeof(Stack)); S->base = (stackelem*)malloc(stack_init_size*sizeof(stackelem)); S->top = S->base; S->size = stack_init_size; } void push_stack(Sqstack &S,stackelem e){ //输入一个stackelem元素进栈 if((S->top - S->base)/sizeof(stackelem)>= S->size){//判断空间是否充足 cout<< "空间不足,追加空间"; S->base = (stackelem*)realloc(S->base,(S->size + stack_add_size)*sizeof(stackelem)); S->top = S->base + S->size; S->size = S->size + stack_add_size; } if(!S->base) return; *S->top++ = e; } void pop_stack(Sqstack &S,stackelem &e){ //取出栈的第一个元素 //S->top是地址 所以e要用&e if (S->top == S->base) return; e = *(--S->top); } bool pass(pos p){ //判断是否是可以通过的地方 if (seat[p.x][p.y]==0) return true; else return false; } /*bool pass(pos p){ //判断是否是可以通过的地方 if (seat[p.x][p.y]==1) return false; else return true; } */ void foot(pos p){ //留下足迹,标明已经来过 seat[p.x][p.y] = 2; } void mark(pos p){ //留下足迹,标明不能通过 seat[p.x][p.y] = 3; } pos next(pos p,int a){ //切换p到相邻的下一位置 if (a==1) p.x,p.y++; if (a==2) p.x++,p.y++; if (a==3) p.x++,p.y; if (a==4) p.x--,p.y--; if (a==5) p.x,p.y--; if (a==6) p.x--,p.y--; if (a==7) p.x--,p.y; if (a==8) p.x--,p.y++; return p; } bool empty_stack(Sqstack &S){ //判断栈是否为空 if (S->top == S->base) return true; else return false; } void print_stack(Sqstack &S) { int a; pos next(pos p,int a); while (!empty_stack(S)) { stackelem e; pop_stack(S,e); cout<<"("<<e.p.x<<","<<e.p.y<<","<<a<<")"<<endl; } } bool main() { //~~~~定义并初始化栈S Sqstack S; init_stack(S); //~~~~定义并初始化开始和结束的位置 pos start={1,1}; pos end={9,8}; pos curpos = start; //当前位置,从(1,1)开始 int curstep=1; //探索的步数,第一步 stackelem e; //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ do{ if(pass(curpos)) { //当前位置可以通过 foot(curpos); //留下足迹 stackelem e(curstep,curpos,0); push_stack(S,e); //把当前位置赋予e并入栈 if (curpos == end) { print_stack(S); system("PAUSE"); return true; //判断是否已经到了出口 } curpos = next(curpos,1); //切换到下一个位置 curstep++; //步数加1 }//if else { //此位置不可通过,到下一方向,如果方向都走遍了即di=8则回退一格 if (!empty_stack(S)){ pop_stack(S,e); //先取出上一个入栈的位置 while (e.di==8 && !empty_stack(S)){ //找到一个有可以通过的方向的位置位置 mark(e.p); //留下不能通过的印记 pop_stack(S,e); }//while if (e.di<8) { //对这个有可以通过的方向的位置做处理--入栈,切换当前位置到相邻位置 e.di++; push_stack(S,e); curpos = next(e.p,e.di); }//if }//if }//else //maze }while(!empty_stack(S)); //while return false; system("PAUSE"); }