/* ****迷宫算法求解************* */
/**计目标：教学演示**************/
#include<stdio.h>
#define rows 10
#define cols 10
typedef struct
{int row;
int col;
}PosType;/* //坐标点结构 */
typedef struct
{int ord;/*//通道块在路径上的“序号” */
PosType seat;/*//通道块在迷宫中的“坐标位置”*/
int di;/*//从此通道快走向下一通道块的“方向” */
}SElemType;/*//栈的元素类型 */
typedef struct
{SElemType *base;
SElemType *top;
int stacksize;
}SqStack;/*//堆栈结构 */
void InitStack(SqStack &s)/*//初始化堆栈 */
{ s.base=(SElemType *)malloc(100*sizeof(SElemType));
if(!s.base) return NULL;
s.top=s.base;
s.stacksize=100;
}
int StackEmpty(SqStack s)/* //栈空判别*/
{return(s.top==s.base);
}
void Pop(SqStack &s ,SelemType &e)/*//弹栈 */
{e=*--s.top);
}
void Push(SqStack &s,SElemType e)/*//将元素压入堆栈*/
{ *s.top++=e;
}
/*static int maze[rows][cols]=
{{0,0,0,0,0,0,0,0,0,0},
{0,1,1,0,1,1,1,0,1,0},
{0,1,1,0,1,0,1,0,1,0},
{0,1,1,0,1,0,0,1,1,0},
{0,1,1,0,0,1,1,1,1,0},
{0,1,1,1,0,1,1,1,1,0},
{0,1,0,1,1,1,0,1,1,0},
{0,1,0,0,0,1,0,0,1,0},
{0,0,1,1,1,1,1,1,1,0},
{0,0,0,0,0,0,0,0,0,0},
}; */
/* //初始迷宫数据（1－通，0－不通）*/
static int maze[rows][cols]=
{{0,0,0,0,0,0,0,0,0,0},
{0,1,1,0,1,1,1,0,1,0},
{0,1,1,0,1,0,1,1,1,0},
{0,1,1,1,0,0,0,0,1,0},
{0,1,0,0,0,1,1,1,1,0},
{0,1,0,1,0,1,0,0,0,0},
{0,1,0,1,1,1,0,1,1,0},
{0,1,0,1,0,0,0,0,1,0},
{0,0,1,1,1,1,1,1,1,0},
{0,0,0,0,0,0,0,0,0,0},
};
/* //初始迷宫数据（1－通，0－不通）*/
static int foot[10][10]={0};/*//标记某点是否走过（1－走过，0－未走过）*/
void printpath(SqStack &s)/*//打印迷宫通路*/
{int i,j;
SElemType e;
while(!StackEmpty(s))
{ Pop(s,e);
foot[e.seat.row][e.seat.col]=1;
}
for(i=0;i<10;i++)
{printf("\n");
for(j=0;j<10;j++)
if(foot[i][j]) printf(" # ");
else printf(" . ");
}
}
int Pass(PosType pos)/*//判断当前的通道块是否可通*/
{
return(maze[pos.row][pos.col]);
};
void FootPrint(PosType pos)
{
maze[pos.row][pos.col]=0;
}
PosType NextPos(PosType curpos,int dir)/*//取当前通道块的下一个通道块*/
{ switch(dir)
{case 1:
curpos.row++;
break;
case 2:
curpos.col++;
break;
case 3:
curpos.row--;
break;
case 4:
curpos.col--;
}
return curpos;/*//将下一个通道块变为当前通道块*/
}
int END(PosType curpos,PosType end)
{return(curpos.row==end.row && curpos.col==end.col);
}
void MazePath(SqStack &s,PosType start,PosType end)
{PosType curpos,nextpos;
int curstep;
SElemType e;
SqStack *s;
s=InitStack();
curpos=start;
curstep=1;
do{
if(Pass(curpos))
{FootPrint(curpos);
e.ord=curstep;e.seat=curpos;e.di=1;
Push(s,e);
if(END(curpos,end)) return s;
curpos=NextPos(curpos,1);
curstep++;
}/* end of if */
else
{ if(!StackEmpty(s))
{ e=Pop(s);
while(e.di==4 && !StackEmpty(s))
{FootPrint(e.seat);/* The same fuction as MarkPrint ? */
e=Pop(s);
}/* end of while */
if(e.di<4)
{e.di++;Push(s,e);
curpos=NextPos(e.seat,e.di);
} /* end of if */
} /* end of if */
} /* end of else */
}while(!StackEmpty(s));
curstep=0;
return NULL;
}
void main()
{SqStack *s;
static PosType start={1,1},end={8,8};
s=MazePath(start,end);
if(s)
printpath(s);
else
printf("\n NO find the path!");
}
