/*如果迷宫有通道可解则正常运行，迷宫不可解为什么显示exe停止工作呢？怎样修改呢？*/
#include
#include
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define COLUMN 10
#define ROW 10
typedef int Status;
typedef struct{
char **maze;
int **footprint;
int row;
int column;
}MazeType;
typedef struct{
int x;
int y;
}PosType;
typedef struct{
int ord;
PosType seat;
int di;
}SElemType;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack *S);
Status InitMaze(MazeType *M);
Status DestroyStack(SqStack *S);
Status ClearStack(SqStack *S);
Status StackEmpty(SqStack S);
int StackLength(SqStack S);
Status GetTop(SqStack S,SElemType *e);
Status Push(SqStack *S,SElemType e);
Status Pop(SqStack *S,SElemType *e);
Status StackTraverse(const SqStack *S);
Status PrintMaze(MazeType *M);
Status MazePath(SqStack *S,MazeType maze,PosType start,PosType end);
Status FootPrint(MazeType *M,PosType pos);
Status Pass(MazeType *M,PosType pos);
SElemType NewSElem(int step,PosType pos,int d);
PosType NextPos(PosType pos,int d);
Status MarkPrint(MazeType *M,PosType pos);
Status PrintFoot(MazeType *M,SqStack *S);
int main()
{
MazeType maze;
SqStack stack;
PosType start,end;
start.x=0;start.y=1;
end.x=8;end.y=9;
InitMaze(&maze);
printf("迷宫形状：\n");
PrintMaze(&maze);
if(TRUE==MazePath(&stack,maze,start,end))
printf("迷宫可解.\n");
else
printf("迷宫不可解.\n");
return 0;
}
Status InitStack(SqStack *S){
//构造一个空栈S
S->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S->base)//分配失败
{
printf("分配内存失败.\n");
exit(0);
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return OK;
}
Status InitMaze(MazeType M){
//初始化迷宫数据
int i,j;
char mz[ROW][COLUMN]={ //mz新定义的二维数组
'#',' ',' ','#','#','#','#','#','#','#',//每行十个
'#','#','#','#',' ',' ',' ','#',' ','#',
'#',' ',' ','#',' ',' ',' ','#',' ','#',
'#',' ',' ',' ',' ','#','#',' ',' ','#',
'#',' ','#','#','#',' ',' ',' ',' ','#',
'#',' ',' ',' ','#',' ','#',' ','#','#',
'#',' ','#',' ',' ',' ','#',' ',' ','#',
'#',' ','#','#','#',' ','#','#',' ','#',
'#','#',' ',' ',' ',' ',' ',' ',' ',' ',
'#','#','#','#','#','#','#','#','#','#'
};
M->maze=(char *)malloc(sizeof(char )*ROW);
M->footprint=(int *)malloc(sizeof(int *)*ROW);
if(!M->maze||!M->footprint){
printf("申请空间失败，迷宫无法初始化.\n");
return ERROR;
exit(0);
}
for(i=0;i
M->maze[i]=(char *)malloc(sizeof(char)*COLUMN);
M->footprint[i]=(int *)malloc(sizeof(int)*COLUMN);
if(!M->maze[i]||!M->footprint[i]){
printf("申请空间失败，迷宫初始化失败.\n");
return ERROR;
exit(0);
}
}
for(i=0;i
for(j=0;j
M->maze[i][j]=mz[i][j];
M->footprint[i][j]=0;
}
}
M->row=ROW;
M->column=COLUMN;
return OK;
}
Status DestroyStack(SqStack *S){
if(!S)
{
printf("指针为空，释放失败.\n");
exit(0);
}
free(S);
return OK;
}
Status ClearStack(SqStack *S){
if(!S)
return FALSE;
S->top=S->base;
return OK;
}
Status StackEmpty(SqStack S){
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
int StackLength(SqStack S){
return S.stacksize;
}
Status GetTop(SqStack S,SElemType *e){
if(S.top==S.base){
printf("栈为空.\n");
return FALSE;
}else{
*e=*(S.top-1);
printf("栈顶元素：%c\n",*e);
return OK;
}
}
Status Push(SqStack *S,SElemType e){
if(S->top-S->base>=S->stacksize){
S->base=(SElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S->base)
{
printf("重新申请空间失败.\n");
exit(0);
}
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*S->top++=e;
return OK;
}
Status Pop(SqStack *S,SElemType *e){
if(S->top==S->base){//栈为空
printf("栈为空.\n");
return ERROR;
}
*e=*(--S->top);
return OK;
}
Status StackTraverse(const SqStack *S){
//从栈底到栈顶依次对每个元素进行访问
SElemType *p=S->base;
if(S->base==S->top)
{
printf("栈为空.\n");
return FALSE;
}
printf("栈中元素：");
while(p!=S->top)
{
printf("x=%d,y=%d\n",p->seat.x,p->seat.y);
*p++;
}
printf("\n");
return OK;
}
Status PrintMaze(MazeType *M){
//输出迷宫
int i,j;
for(i=0;irow;i++){
for(j=0;jcolumn;j++){
printf("%c",M->maze[i][j]);
}
printf("\n");
}
printf("\n");
return OK;
}
Status PrintFoot(MazeType *M,SqStack *S){
//输出迷宫的路径
int i,j;
SElemType *p;
for(i=0;irow;i++){
for(j=0;jcolumn;j++){
M->footprint[i][j]=0;
}
}
p=S->base;
if(S->base==S->top)
{
printf("栈为空.\n");
return FALSE;
}
while(p!=S->top)
{
M->footprint[p->seat.x][p->seat.y]=1;
*p++;
}
for(i=0;irow;i++){
for(j=0;jcolumn;j++){
printf("%d",M->footprint[i][j]);
}
printf("\n");
}
return OK;
}
Status MazePath(SqStack *S,MazeType maze,PosType start,PosType end){
int curstep=1;//当前步数
SElemType e;
PosType curpos=start;//当前位置
InitStack(S);//初始化栈
do{
if(TRUE==Pass(&maze,curpos)){
FootPrint(&maze,curpos);
e=NewSElem(curstep,curpos,1);
Push(S,e);
if((curpos.x==end.x)&&(curpos.y==end.y)){//到达终点（出口）
printf("迷宫路径:\n");
//StackTraverse(S);
PrintFoot(&maze,S);
return TRUE;
}
curpos=NextPos(curpos,1);
curstep++;
}//if
else{//当前位置不能通过
if(!StackEmpty(*S)){
Pop(S,&e);
while(e.di==4&&!StackEmpty(*S)){
MarkPrint(&maze,e.seat);
Pop(S,&e);
}//while
if(e.di<4){
e.di++;
Push(S,e);
curpos=NextPos(e.seat,e.di);
}//if
}//if
}//else
//PrintFoot(&maze,S);
}while(!StackEmpty(*S));//一直循环到栈空为止
return FALSE;
}
Status FootPrint(MazeType *M,PosType pos){
//将迷宫的当前位置pos设置为"走过"，即footprint该位置为1
if((pos.x>M->row)||(pos.y>M->column))//检验大小
return FALSE;
M->footprint[pos.x][pos.y]=1;//如果不满足条件,开始运行下一步
return TRUE;
}
Status Pass(MazeType *M,PosType pos){
//判断当前位置是否可通，即为走过的通道块
if((M->rowcolumn
printf("位置越位.\n");
exit(0);
}
if((0==M->footprint[pos.x][pos.y])&&(M->maze[pos.x][pos.y]==' '))
return TRUE;
else
return FALSE;
}
SElemType NewSElem(int step,PosType pos,int d){
//创建新结点，用step，pos，d初始化该结点
SElemType e;
e.ord=step;
e.seat=pos;
e.di=d;
return e;//下一步
}
PosType NextPos(PosType pos,int d){
//获取pos位置d方向的位置
switch(d){
case 1://东
pos.x++;
break;
case 2://南
pos.y++;
break;
case 3://西
pos.x--;
break;
case 4://北
pos.y--;
break;
default:
printf("位置编号出错.\n");
}//利用坐标左西右东上北下南
return pos;
}
Status MarkPrint(MazeType *M,PosType pos){
//将迷宫M的pos位置，设为已走，成功返回OK；否则返回ERROR
if(pos.x>M->row||pos.y>M->column){
printf("所要标记位置越位.\n");
return ERROR;
}
M->footprint[pos.x][pos.y]=1;
return OK;
}
