C语言 利用顺序栈进行迷宫求解 求修改
我重新发一贴吧,向各位求助!!!我的程序在主函数的输入时存在错误,本来是想要以矩阵输入,可是输的位数不对,求解?不知道如何处理
还有不知道InitStack能不能初始化,麻烦修改一下。
大神们,有没有很棒的C语言的迷宫求解的版本,求
#include<stdio.h>
#include<stdlib.h>
#define STACK_INIT_SIZE 50
#define STACKINCREMENT 2
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef struct
{
int x ;
int y ;
int di;
}PosType;
typedef struct
{
PosType *base;
PosType *top;
int stacksize;
}SqStack;
int InitStack(SqStack *S)
{ printf("1\n");
S->base =(PosType *)malloc(STACK_INIT_SIZE * sizeof(PosType));
printf("2\n");
if(!S->base) exit(0);
printf("3\n");
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return OK;
}
int DestroyStack(SqStack * S)
{
free(S->base);
S->base=NULL;
S->top=NULL;
S->stacksize=0;
return OK;
}
int ClearStack(SqStack *S)
{
S->top=S->base;
return OK;
}
int StackEmpty(SqStack *S)
{
if(S->top==S->base)return TRUE;
else return FALSE;
}
int GetTop(SqStack *S,PosType *e)
{
if(S->top==S->base)
return ERROR;
*e=*(S->top-1);
return OK;
}
int push(SqStack *S,PosType* e)
{
if(S->top - S->base >= S->stacksize)
{
S->base=(PosType *)realloc(S->base,(S->stacksize+STACKINCREMENT)* sizeof(PosType));
if(!S->base) exit(-1);
S->top=S->base+S->stacksize;
S->stacksize +=STACKINCREMENT;
}
*S->top++=*e;
return OK;
}
int pop (SqStack *S,PosType *e)
{
if(S->top==S->base)
return ERROR;
*e=*--S->top;
return OK;
}
void reverseprint(SqStack *S,PosType *end)
{
while(S->base!=S->top)
{
printf("(%d,%d,%d)->",S->base->x,S->base->y,S->base->di);
S->base++;
}
printf("(%d,%d,%d)\n",end->x,end->y,end->di);
}
int Migong(int *p,SqStack *S,PosType *start,PosType *end,int e,int r)
{
static int i=1;
PosType a,*b;
a =*start;
b=&a;
while(!StackEmpty(S))
{
if( *(p +( a.x * e )+a.y) ==0 )
{
push(S, b);
if(a.x == end->x && end->y ==a.y ) return TRUE;
a.x=a.x+1;
a.di=1;
}
else
{
if(!StackEmpty(S))
{
pop(S,b);
while(a.di == 4 && !StackEmpty(S))
{
pop(S,b);
}
if(a.di<4)
{
a.di++;
push(S,b);
switch(a.di)
{
case 2:a.y=a.y+1;break;
case 3:a.x=a.x-1;break;
case 4:a.y=a.y-1;break;
}
}
}
printf("第%d条路径:",i++);
reverseprint(S,end);
}
return FALSE;
}
}
void main()
{
int a,b,c,d,i,j,r1,r2;
int *p;
int mg[10][10];
PosType *m,*n;
SqStack *S;
printf("请输入迷宫的长和宽\n");
scanf("%d,%d",&r1,&r2);
printf("请输入迷宫的图案(通:0 ;不通:1 )\n");
for(i=0;i<r1;i++)
for(j=0;j<r2;j++)
{
scanf("%d ",&mg[i][j]);
}
p=&mg[0][0];
printf("请输入迷宫的入口,出口((a,b))\n");
scanf("%d,%d",&a,&b,&c,&d);
m->x=a-1;
m->y=b-1;
n->x=c-1;
n->y=d-1;
m->di=1;
InitStack(S);
if(!Migong(p,S,m,n,r1,r2))
printf("走不通\n");
else
{while(S->base != S->top)//直到走完所有的方向
{
pop(S,m);
if(m->di <= 4)
{
m->di++;
Migong(p,S,m,n,r1,r2);
}
}
}
}