#include "3_3_2.h"
#include "SqStack.h"
/* 利用栈求解迷宫问题（只输出一个解，算法3.3） */
#define MAXLENGTH 25 /* 设迷宫的最大行列为25 */
typedef int MazeType[MAXLENGTH][MAXLENGTH]; /* 迷宫数组[行][列] */
/* 全局变量 */
MazeType m; /* 迷宫数组 */
int curstep=1; /* 当前足迹,初值为1 */
/* 定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹 */
Status Pass(PosType b)
{ /* 当迷宫m的b点的序号为1(可通过路径)，return OK; 否则，return ERROR。 */
if(m[b.x][b.y]==1)
return OK;
else
return ERROR;
}
void FootPrint(PosType a)
{ /* 使迷宫m的a点的序号变为足迹(curstep) */
m[a.x][a.y]=curstep;
}
PosType NextPos(PosType c,int di)
{ /* 根据当前位置及移动方向，返回下一位置 */
PosType direc[4]={{0,1},{1,0},{0,-1},{-1,0}}; /* {行增量,列增量} */
/* 移动方向,依次为东南西北 */
c.x+=direc[di].x;
c.y+=direc[di].y;
return c;
}
void MarkPrint(PosType b)
{ /* 使迷宫m的b点的序号变为-1(不能通过的路径) */
m[b.x][b.y]=-1;
}
/* 算法3.3 */
Status MazePath(PosType start,PosType end)
{
/* 若迷宫maze中存在从入口start到出口end的通道，则求得一条 */
/* 存放在栈中(从栈底到栈顶)，并返回TRUE；否则返回FALSE */
SqStack S; //定义一个堆栈
PosType curpos; //坐标数据
SElemType e; //堆栈元素类型
InitStack(&S); //初始化堆栈
curpos=start; //开始进入迷宫的坐标
//走迷宫的过程
do
{
/* 当前位置可以通过，即是未曾走到过的通道块 */
if(Pass(curpos))
{
FootPrint(curpos); /* 留下足迹 */
//下面的步骤将 e 元素压入堆栈，它包括
e.ord=curstep; //记录足迹编号，就是第几步了
e.seat.x=curpos.x; //记录迷宫坐标
e.seat.y=curpos.y;
e.di=0; //记录方向，0，1，2，3分别代表 东南西北
Push(&S,e); /* 入栈当前位置及状态 */ //S是堆栈变量，e是堆栈元素
curstep++; /* 足迹加 1 */
//判断是否已到达出口
if(curpos.x ==end.x && curpos.y==end.y) /* 到达终点(出口) */
return TRUE;
//如果未到达出口
//判断下一步应该走向哪里，参数是 当前位置curpos，和当前方向
curpos=NextPos(curpos,e.di);
}
/* 当前位置不能通过 */
else
{
if(!StackEmpty(S))
{
Pop(&S,&e); /* 退栈到前一位置 */
curstep--;
while(e.di==3 && !StackEmpty(S)) /* 前一位置处于最后一个方向(北) */
{
MarkPrint(e.seat); /* 留下不能通过的标记(-1) */
Pop(&S,&e); /* 退回一步 */
curstep--;
}
if(e.di<3) /* 没到最后一个方向(北) */
{
e.di++; /* 换下一个方向探索 */
Push(&S,e);
curstep++;
curpos=NextPos(e.seat,e.di); /* 设定当前位置是该新方向上的相邻块 */
}
}
}
}while(!StackEmpty(S));
return FALSE;
}
void Print(int x,int y)
{ /* 输出迷宫的解 */
int i,j;
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
{
if(m[i][j]==1)
printf(" ",m[i][j]);
else if(m[i][j]==0)
printf("█",m[i][j]);
else if(m[i][j]==-1)
printf("-");
else
printf("*");
}
printf("\n");
}
}
void Print2(int x,int y)
{ /* 输出迷宫的解 */
int i,j;
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
{
printf("%3d",m[i][j]);
}
printf("\n");
}
}
void main()
{
PosType begin,end;
int i,j,x,y,x1,y1;
PosType wall[18]={\
{1,3},{1,7},{2,3},{2,7},{3,5},{3,6},\
{4,2},{4,3},{4,4},{5,4},{6,2},{6,6},\
{7,2},{7,3},{7,4},{7,6},{7,7},{8,1}\
};
printf("严蔚敏数据结构算法 3_3改进程序\n");
printf("走迷宫，迷宫数据从数组给出，不用从键盘输入\n\n");
//x表示行，y表示列
x=10;
y=10;
printf("迷宫的行数%d,列数%d(包括外墙)：\n",x,y);
//下面的语句是把迷宫围起来，像书上的图那样
for(i=0;i<x;i++) /* 定义周边值为 0(同墙) */
{
m[0][i]=0; /* 行周边 */
m[x-1][i]=0;
}
for(j=1;j<y-1;j++)
{
m[j][0]=0; /* 列周边 */
m[j][y-1]=0;
}
for(i=1;i<x-1;i++)
for(j=1;j<y-1;j++)
m[i][j]=1; /* 定义通道初值为1 */
j=18;
printf("迷宫内墙单元数：%d\n",j);
printf("从数组读入，迷宫内墙每个单元的行数,列数：\n\n");
for(i=0;i<j;i++)
{
x1=wall[i].x;
y1=wall[i].y;
m[x1][y1]=0; /* 定义墙的值为0 */
}
printf("迷宫结构如下:\n");
Print(x,y);
printf("\n");
begin.x=1; begin.y=1;
printf("起点的行数%d,列数%d：\n",begin.x,begin.y);
end.x=8; end.y=8;
printf("终点的行数%d,列数%d：\n\n",end.x,end.y);
if(MazePath(begin,end)) /* 求得一条通路 */
{
printf("此迷宫从入口到出口的一条路径如下:\n");
Print(x,y); /* 输出此通路 */
}
else
printf("此迷宫没有从入口到出口的路径\n");
printf("\n另外一种迷宫输出方式:\n");
printf("此迷宫从入口到出口的一条路径如下:\n");
Print2(x,y); /* 输出此通路 */
printf("按任意键结束程序...");
getch();
}
