迷宫课设 100%原创 C描述
typedef struct StackNode
{
ElemType data;
StackNode *next;
)StackNode, *LinkType; //结点类型，指针类型
typedef struct
{
LinkType top;
int size;
}Stack; //栈类型
//栈的基本操作如下
Status InitStack(Stack &s)
{
s.top=NULL;
s.size=0;
return ok;
}
Status Push(Stack &s,ElemType e)
{
p=(LinkType*)malloc( sizeof(StackNode) );
if(!p) return FALSE;
p.data=e;
p.next=s.top;
s.top=p;
s.size++;
return TURE;
}
Status StackEmpty(Stack &s)
{
if(s.top==NULL) return TURE;
else return FALSE;
}
Status GetTop(Stack &s,ElemType e)
{
if( s.top==NULL ) return ERROR;
e=s.top->data;
return OK;
}
Status Pop(Stack &s)
{
if( s.top==NULL ) return ERROR;
p=s.top;
s.top=p->next;
s.size--;
free(p);
return OK;
}
Status DestroyStack(Stack &s)
{
free(s);
return Ok;
}
//栈的基本操作如上
//迷宫类型
typedef struct
{
int x,y; //表示点的方位
int Live; //Live=1,该点可走，Live=0,该点不可走，Live=2表示该点是解
int direction=10; //direction 表示当前点探索的方向,direction 初始10表示该点未探索任何方向
int count=1; //count表示当前点探索方向次数
}MazeType maze[M*N];
//迷宫基本操作如下
status InitMaze(MazeType &maze) //初始化迷宫,为方便操作,迷宫外设了一圈围墙
{
for(j=0;j<=N-1;j++)
{
maze[j].Live=0;
maze[j].x=j;
maze[j].y=0;
maze[ (M-1)*N+j ].Live=0;
maze[ (M-1)*N+j ].x=j;
maze[ (M-1)*N+j ].y=M-1;
}
for(i=1;i<=M-2;i++)
{
maze[i*N].Live=0;
maze[i*N].x=0;
maze[i*N].y=i;
maze[ i*N+N-1 ].Live=0;
maze[ i*N+N-1 ].x=N-1;
maze[ i*N+N-1 ].y=i;
) //初始化围墙部分
printf("Input Maze:0 stand for unclear,1 stand for clear\n");
for(i=1;i<=M-2;i++)
for(j=1;j<=N-2;j++)
{
maze[ N*i+j ].x=j;
maze[ N*i+j ].y=i;
scanf( maze[ N*i+j ].Live ); //用户输入迷宫部分
}
if(maze[N+1].Live==0)
{
maze[N+1].Live=1;
printf("Sorry,(1,1)must be initialized alive");
}
return ok;
}
Status MazeSolve(MazeType &maze) //求解M*N的迷宫
{
k=2;
InitStack(s);
Push(s,N+1);
while( !StackEmpty(s) )
{
GetTop(s,cur);
while( maze[cur].count<=3)
{
if(cur==Arrival) { Answer(maze,s); return ok; } //Arrival 目的地编号
if( maze[cur].direction!=10 ) k=maze[cur].direction;
m=MD[k].next;
maze[cur].direction=m;
next_number=Number( maze[cur].x, maze[cur].y, m);
maze[cur].count++;
if( maze[next_number].Live==1 )
{
Gone=m;
Push(s,next_number);
break;
}
}
if( maze[cur].count==4 ) Pop(s);
else k=Transform(Gone);
}
printf("No Path");
DestroyStack(s);
return ERROR;
}
Status Answer( MazeType &maze,Stack s ) // 确定最终路径,更新Live值
{
while( !StackEmpty(s) )
{
Pop(s,e);
maze[e].Live=2;
}
DestroyStack(s);
return ok;
}
Status Print( MazeType &maze ) //打印结果
{
count=0;
k=1;
while(count<=M*N-1)
{
switch( maze[count].Live )
{ //0代表不通,1代表通,*代表路径
case 0: printf("0");
case 1: printf("1");
case 2: printf("*");
}
if( k%N==0 ) printf("\n");
k++;
}
return OK;
}
//迷宫基本操作如上
//方向类型
typedef struct
{
int next;
}MoveDirection MD[4];
//方向的基本操作如下
Status InitMoveDirection(&MD) //North=0,South=1,West=2,East=3
{
for(k=0;k<=2;k++)
{
MD[k].next=k+1;
}
MD[3].next=0;
return ok;
}
int Transform(int Gone) //Gone表示来的方向
{ //函数的功能是返回与Gone相反的方向
if( Gone%2==0 ) return Gone+1;
else return Gone-1;
}
//方向的基本操作如上
int Number(int x,int y,int direction) //根据移动方向和当前点位置确定下个点编号
{
switch (direction)
{
case 0: return N*(y-1)+x;
case 1: return N*(y+1)+x;
case 2: return N*y+x-1;
case 3: return N*y+x+1;
}
}
#define M=10;
#define N=10;
int main()
{
MazeType maze[M*N];
InitMaze(maze);
printf("Maze Below:");
Print(maze);
MazeSolve(maze);
printf("Maze Sovled Below:");
Print(maze);
return 0;
}
