十二集
2016-12-19 12:17
采纳率: 66.7%
浏览 2.2k
已采纳

这是一个迷宫求解问题

/*如果迷宫有通道可解则正常运行,迷宫不可解为什么显示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;
}

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • threenewbee 2016-12-19 16:29
    已采纳
    已采纳该答案
    打赏 评论
  • 十二集 2016-12-20 02:45

    我发的那个代码如果迷宫可解,可以通的话运行起来没有问题,问题是已经编写了不解时的情况下的处置但是貌似没有发挥作用就只有这个问题了,不可解通不了就会停止运行,能解决吗?

    打赏 评论

相关推荐 更多相似问题