问题描述
- 迷宫问题求用一个更好的办法代替两个栈
-
#include
#include
#define M 20 //最大行数
#define N 20 //最大列数
struct mark //定义迷宫内点的坐标类型
{
int x; //行值
int y; //列值
};struct Element //链栈元素结点
{
int x,y; //x行,y列
int d; //d下一步的方向
};struct LStack //链栈
{
Element elem;
struct LStack *next; //指针变量
};typedef LStack *PLStack;
/*……………………………栈函数……………………………*/
int InitStack(PLStack &S)//构造空栈
{
S=NULL;
return 1;
}int StackEmpty(PLStack S)//判断栈是否为空
{
if(S==NULL)
return 1;
else
return 0;
}int Push(PLStack &S, Element e)//压入新数据元素
{
PLStack p;
p=(PLStack)malloc(sizeof(LStack));
p->elem=e;
p->next=S;
S=p;
return 1;
}int Pop(PLStack &S,Element &e) //栈顶元素出栈
{
PLStack p;
if(!StackEmpty(S))
{
e=S->elem;
p=S;
S=S->next;
free(p);
return 1;
}
else
return 0;
}/*……………………求迷宫路径函数……………………………*/
void MazePath(struct mark start,struct mark end,int maze[M][N],int Direction[4][2])
{
int i,j,d;int a,b;
Element elem,e;
PLStack S1, S2; //定义两个栈
InitStack(S1);
InitStack(S2);
maze[start.x][start.y]=2; //入口点作上标记
elem.x=start.x;
elem.y=start.y;
elem.d=-1; //开始为-1
Push(S1,elem);
while(!StackEmpty(S1)) //栈不为空 有路径可走
{Pop(S1,elem);
i=elem.x; //入口横坐标
j=elem.y; //入口纵坐标
d=elem.d+1;//下一个方向
while(d<4) //试探各个方向
{
a=i+Direction[d][0];
b=j+Direction[d][1];/*如果到了出口*/if(a==end.x && b==end.y && maze[a][b]==0)
{
elem.x=i;
elem.y=j;
elem.d=d;Push(S1,elem);//让出口前的最后一步进栈
elem.x=a;
elem.y=b;
elem.d=666; //方向输出为-1 判断是否到了出口
Push(S1,elem);
printf("n括号内第三位数字n0代表向右移动一格 1代表向下 2代表向左 3代表向上n666为则走出迷宫nn通路为:(行坐标,列坐标,方向)n");
while(S1) //逆置序列 并输出迷宫路径序列
{
Pop(S1,e);
Push(S2,e);
}
while(S2)
{
Pop(S2,e);
printf("-->(%d,%d,%d)",e.x,e.y,e.d);
}
return; //用break,出错，exit会结束程序，选用return
}/*找到可以前进的非出口的点*/if(maze[a][b]==0)
{
maze[a][b]=2; //标记走过此点
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem); //当前位置入栈
i=a; //下一点转化为当前点
j=b;
d=-1;
}d++;
}
}
printf("该路径中有断路，无法走出n");
}/*建立迷宫*/void initmaze(int maze[M][N])
{
int i,j;
int m,n; //迷宫行,列printf("请输入迷宫的行数 m=n"); //输入迷宫
scanf("%d",&m);
printf("请输入迷宫的列数 n=n");
scanf("%d",&n);
printf("n请输入迷宫的各行各列:n用空格隔开,0代表路,1代表墙nn",m,n);
for(i=1;i<=m;i++)
{
printf("第%d行迷宫设置：",i);
for(j=1;j<=n;j++)
scanf("%d",&maze[i][j]);
}printf("*************************所建立的迷宫为****************************n");
for(i=0;i<=m+1;i++) //加一圈坐标和围墙
{
maze[i][0]=i; //行坐标
maze[i][n+1]=1;
}
for(j=0;j<=n;j++)
{
maze[0][j]=j; //列坐标
maze[m+1][j]=1;
}for(i=0;i<=m+1;i++) //输出迷宫
{
for(j=0;j<=n+1;j++)
printf("%d ",maze[i][j]);
printf("n");
}
}void main()
{
printf("*****************漫步迷宫*******************n");int sto[M][N];
struct mark start,end; //start,end入口和出口的坐标
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次为上下左右initmaze(sto);//建立迷宫
printf("输入入口的横坐标,纵坐标[逗号隔开]n");
scanf("%d,%d",&start.x,&start.y);
printf("输入出口的横坐标,纵坐标[逗号隔开]n");
scanf("%d,%d",&end.x,&end.y);MazePath(start,end,sto,add); //寻找路径
printf("n");
}
解决方案
你得栈可以使用双向链表或者数组，就可以使用一个栈