#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 10000
#define STACKINCREMENT 110
#define M 11
#define N 10
int flag=0;
typedef struct//坐标位置
{
int x;//行
int y;//列
}PosType;//坐标位置类型
typedef struct//栈中元素结构体
{
int ord;//通道块在路径上的“序号
PosType seat;//通道块在迷宫里的“坐标位置”
int di;//通道方向(1东2南3西4北)
}SElemType;//栈的元素类型
typedef struct//栈
{
SElemType *base;
SElemType *top;
int stacksize;////当前已分配的存储空间，以元素为单位
}SqStack;
//栈操作
void initialStack(SqStack *s)//栈的建立
{
s->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!s->base) exit(0);////存储分配失败
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,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType));
if(!s->base) exit(0);
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;
}
(*(s->top)).ord=e.ord;
(*(s->top)).seat.x=e.seat.x;
(*(s->top)).seat.y=e.seat.y;
(*(s->top)).di=e.di;
s->top++;
}
void Pop(SqStack *s,SElemType *e)//删除栈顶元素 用e返回
{
if(s->top==s->base) exit(0);
(s->top)--;
e->ord=(*(s->top)).ord;
e->seat.x=(*(s->top)).seat.x;
e->seat.y=(*(s->top)).seat.y;
e->di=(*(s->top)).di;
}
int StackEmpty(SqStack *s)//检查栈是否为空
{
if(s->top==s->base) return(1);
else return(0);
}
void ClearStack(SqStack *s)//将s栈清空
{
s->top=s->base;
s->stacksize=0;
}
//初始化迷宫
void initmaze(int maze[M][N])
{
int i,j;
int m,n; //迷宫行,列 [/M]
printf("请输入迷宫的行数 m=");
scanf("%d",&m);
printf("请输入迷宫的列数 n=");
scanf("%d",&n);
printf("\n请输入迷宫的各行各列:\n用空格隔开,0代表路,1代表墙\n",m,n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&maze[i][j]);
printf("你建立的迷宫为(最外圈为墙)...\n");
for(i=0;i<=m+1;i++) //加一圈围墙
{
maze[i][0]=8;
maze[i][n+1]=8;
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=8;
maze[m+1][j]=8;
}
for(i=0;i<=m+1;i++) //输出迷宫
{
for(j=0;j<=n+1;j++)
printf("%d ",maze[i][j]);
printf("\n");
}
}
void NextPos(PosType *p,int d)//确定下一个位置的坐标
{
switch(d)
{
case 1:p->y++;break;//右东
case 2:p->x++;break;//下南
case 3:p->y--;break;//左西
case 4:p->x--;break;//上北
}
}
void MazePath(int (*maze)[N])
{
int curstep;
int x,y;
int mark[M][N]={0};
SqStack s;
PosType curpos;
SElemType e;//栈中元素结构体 1.序号;2.坐标位置;3.通道方向
initialStack(&s);
printf("请输入入口坐标x,y:");
scanf("%d%d",&curpos.x,&curpos.y); //设定入口
curstep=1;//探索第一步
do
{
if((!maze[curpos.x][curpos.y])&&(!mark[curpos.x][curpos.y]))
{
mark[curpos.x][curpos.y]=1;
e.ord=curstep;
e.seat.x=curpos.x;
e.seat.y=curpos.y;
e.di=1;
Push(&s,e);
if((curpos.x==M-2)&&(curpos.y==N-2))
{
flag=1;
printf("走出迷宫的一条坐标路径为:\n[终点]");
while(!StackEmpty(&s))
{
Pop(&s,&e);
printf("<--(%d,%d)",e.seat.x,e.seat.y);
}
printf("<--[起点]");
printf("\n");
ClearStack(&s);
}
NextPos(&curpos,1);//下一个位置是当前位置的东邻
curstep++;//探索下一步
}
else
{
if(!StackEmpty(&s))
Pop(&s,&e);//留下不能通过的标记
while(e.di==4&&!StackEmpty(&s))//栈不空但是栈顶位置四周均不通
{
mark[e.seat.x][e.seat.y]=1;
Pop(&s,&e);
}
if(e.di<4)
{
e.di++;
Push(&s,e);;//换下一个方向探索
curpos.x=e.seat.x;
curpos.y=e.seat.y;
NextPos(&curpos,e.di);//设定当前位置是该新方向上的相邻块
}
}
}while(!StackEmpty(&s));
}
void main()
{
int maze[M][N];
PosType curpos;
initmaze(maze[M][N]);
MazePath(maze);
printf("输入入口的横坐标,纵坐标[逗号隔开]\n");
scanf("%d,%d",&curpos.x,&curpos.y);
printf("输入出口的横坐标,纵坐标逗号隔开]\n");
scanf("%d,%d",&curpos.x,&curpos.y);
if(flag==0)
printf("该迷宫不能走出去!\n");
}
我编译没错，但是不知道组建哪里错了
2016-03-21 13:12
