迷宫问题实验报告

迷宫问题 代码描述： #include \"stdio.h\" #include \"stdlib.h\" #define TRUE 1 #define FALES 0 #define OK 1 #define ERROR 0 #define OVERFLOW 0 #define INFEASIBLE -1 #define stack_init_size 100 #define stackincrement 10 typedef struct /*迷宫中的坐标*/ { int x; int y; }postype;

typedef struct {

postype seat; /*通道块在迷宫中的坐标位置*/ int di; /*从此通道走向下一通道块的方向*/ }selemtype;

typedef struct /*定义顺序栈存储结构*/ {

selemtype *base; selemtype *top; int stacksize; }sqstack;

typedef struct {

int data; /*判断迷宫，通道为0，墙为1*/

int flag; /*标志，未走过或通道为0，走过或墙为1*/ }melem;

melem maze[10][10]={{{1,1},{1,1},{1,1},{1,1},{1,1},{1,1},{1,1},{1,1},{1,1},{1,1}},

{{1,1},{0,0},{0,0},{1,1},{0,0},{0,0},{0,0},{1,1},{0,0},{1,1}}, {{1,1},{0,0},{0,0},{1,1},{0,0},{0,0},{0,0},{1,1},{0,0},{1,1}}, {{1,1},{0,0},{0,0},{0,0},{0,0},{1,1},{1,1},{0,0},{0,0},{1,1}},

{{1,1},{0,0},{1,1},{1,1},{1,1},{0,0},{0,0},{0,0},{0,0},{1,1}}, {{1,1},{0,0},{0,0},{0,0},{1,1},{0,0},{0,0},{0,0},{0,0},{1,1}}, {{1,1},{0,0},{1,1},{0,0},{0,0},{0,0},{1,1},{0,0},{0,0},{1,1}}, {{1,1},{0,0},{1,1},{1,1},{1,1},{0,0},{1,1},{1,1},{0,0},{1,1}}, {{1,1},{1,1},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{1,1}}, {{1,1},{1,1},{1,1},{1,1},{1,1},{1,1},{1,1},{1,1},{1,1},{1,1}},}; /*最外一层为墙*/

void initstack(sqstack *s) /*构造一个空栈s*/ {s->base=(selemtype * )malloc(stack_init_size * sizeof(selemtype));

if(!s->base) {printf(\"构造空栈出错!\");exit(OVERFLOW);} s->top=s->base;

s->stacksize=stack_init_size; }

void push(sqstack *s,selemtype e) /*插入元素e为新的栈顶元素*/

{if(s->top-s->base>=s->stacksize) {s->base=(selemtype

* )realloc(s->base,(s->stacksize+stackincrement) * sizeof(selemtype));

if(!s->base) {printf(\"插入错误!\");exit(OVERFLOW);}

s->top=s->base+s->stacksize; s->stacksize+=stackincrement; }

*(s->top++)=e; }

selemtype pop(sqstack *s) /*若栈不空，则删除s的栈顶元素，用e返回其值*/ {

selemtype e;

if(stackempty(s)) {printf(\"堆栈为空!\");exit(OVERFLOW);} e=*(--s->top); return e; }

int stackempty(sqstack *s) /*判断栈是否为空*/ {

if(s->base==s->top) return TRUE; else return FALES; }

int pass(postype e) /*判断当前位置是否曾经走过*/

{

if(maze[e.x][e.y].data==0&&maze[e.x][e.y].flag==0) return 1;

else return 0; }

void footprint(postype e) /*留下足迹*/ {

maze[e.x][e.y].flag=1; }

postype nextpos(postype e,int n) {switch(n) {

case 1:e.y++;break; case 2:e.x++;break; case 3:e.y--;break; case 4:e.x--; } return e; }

int mazepath()/*若迷宫maze中存在从入口到出口的通道，则求得一条存放在栈中，并把栈输出*/

{

sqstack *s=NULL,*p=NULL; selemtype e;

postype curpos={1,1},end={8,8};/*输入迷宫入口和出口坐标*/ s=(sqstack * )malloc(sizeof(sqstack)); initstack(s); do {

if (pass(curpos)) /*判断当前位置是否为曾经走过的通道块*/ {

footprint(curpos);/*留下足迹*/ e.seat=curpos; e.di=1;

push(s,e); /*加入路径*/

if(curpos.x==end.x&&curpos.y==end.y) break;/*如果到达出口*/

curpos=nextpos(curpos,1); /*下一位置是当前位置的东邻*/ }

else /*当前位置不能通过*/ {

if(!stackempty(s))

{

e=pop(s);

while(e.di==4&&!stackempty(s)) e=pop(s); /*退回一步*/ if(e.di<4) {

e.di++; /*换一方向探索*/ push(s,e);

curpos=nextpos(e.seat,e.di); /*设定当前位置是该新方向上的相邻块*/ } } }

}while(!stackempty(s));

p=(sqstack * )malloc(sizeof(sqstack)); initstack(p); while(!stackempty(s)) push(p,pop(s)); while(!stackempty(p)) {

e=pop(p);

printf(\"(%d,%d)->\ } }

void printmaze()/*输出迷宫图形*/ { int i,j;

for(i=0;i<10;i++) {

printf(\"\\n\\n\"); for(j=0;j<10;j++) printf(\"%d \ }

printf(\"\\n\\n\\n\\n\\n\"); } main() { clrscr();

printf(\"迷宫图形如下:\\n\"); printmaze();

printf(\"走出迷宫路径如下:\\n\"); mazepath(); getch(); } 测试运行： 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 the root is:

<1,1>-><1,2>-><2,2>-><3,2>-><3,1>-><4,1>-><5,1>-><5,2>-><6,3>-><6,4>-><6,5>-><7,5>-><8,5>-><8,6>-><8,7>-><8,8>->