求高手 迷宫课设 帮忙纠错
求高手
typedef struct StackNode
{
int data;
struct StackNode *next;
} StackNode, *StackPtr; /* 结点类型，指针类型 */
typedef struct
{
StackPtr top;
int size;
} Stack; /* 栈类型 */
typedef struct /* 迷宫类型 */
{
int x,y; //表示点的方位
int Live; //Live=1,该点可走，Live=0,该点不可走，Live=2表示该点是解
int direction; //direction 表示当前点探索的方向,direction 初始10表示该点未探索任何方向
int count; //count表示当前点探索方向次数
} MazeType;
//方向类型
typedef struct
{
int next;
} MoveDirection;
#if !defined( NULL )
#define NULL ( 0 )
#endif
#define M 10
#define N 10
#include <stdio.h>
#include <cstdlib>
/* 1.栈的实现 */
void InitStack( Stack &s )
{
s.top = NULL;
s.size = 0;
}
void Push( Stack &s, int e )
{
StackPtr p;
p = ( StackPtr ) malloc ( sizeof( StackNode ) );
if(!p) exit( -1 );
p->data = e;
p->next = s.top;
s.top = p;
s.size++;
}
int StackEmpty( Stack &s )
{
if( s.top == NULL ) return 1;
else return 0;
}
int GetTop( Stack &s, int &e )
{
if( s.top == NULL ) return 0;
e = s.top->data;
return 1;
}
int Pop( Stack &s )
{
StackPtr p;
if( s.top == NULL ) return 0;
p = s.top;
s.top = p->next;
s.size--;
free( p );
return 1;
}
void DestroyStack( Stack &s )
{
free( s.top );
}
/* 1.栈的实现如上 */
/* 2.迷宫实现 */
void InitMaze( MazeType &maze ) //初始化迷宫,为方便操作,迷宫外设了一圈围墙
{
int j;
int i;
for( j = 0; j <= N-1; j++ )
{
maze[ j ].Live = 0;
maze[ j ].x = j;
maze[ j ].y = 0;
maze[ j ].direction = 10;
maze[ j ].count = 1;
maze[ (M-1)*N+j ].Live = 0;
maze[ (M-1)*N+j ].x = j;
maze[ (M-1)*N+j ].y = M-1;
maze[ (M-1)*N+j ].direnction = 10;
maze[ (M-1)*N+j ].count = 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 ].direction = 10;
maze[ i*N ].count = 1;
maze[ i*N+N-1 ].Live = 0;
maze[ i*N+N-1 ].x = N-1;
maze[ i*N+N-1 ].y = i;
maze[ i*N+N-1 ].direnction = 10;
maze[ i*N+N-1 ].count = 1;
} //初始化围墙部分
printf( "Input Maze:0 stand for no way, 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( "&d", maze[ N*i+j ].Live );
//用户输入迷宫部分
}
}
if( maze[ N+1 ].Live == 0 )
{
maze[N+1].Live = 1;
printf( "Sorry,(1,1) must be initialized alive\n" );
}
if( maze[ 8 * ( N+1 ) ].Live == 0 )
{
maze[ 8 * ( N+1 ) ].Live = 1;
printf( "Sorry,(8,8) must be initialized alive\n" );
}
}
void Answer( MazeType &maze, Stack &s )
{
int e;
while( !StackEmpty( s ) )
{
Pop( s, e );
maze[ e ].Live = 2;
}
DestroyStack( s );
}
int MazeSolve( MazeType &maze, Stack &s, MoveDirection &MD )
{ /* 求解M*N的迷宫 */
int k = 2;
int m;
int next_number;
int Gone;
int cur;
int Arrival = 88;
InitStack( s );
Push( s, N+1 );
while( !StackEmpty( s ) )
{
GetTop( s,cur );
while( maze[ cur ].count <=3 )
{
if( cur == Arrival ) { Answer( maze,s ); return 1; } //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 );
}
DestroyStack( s );
return 0;
}
void Print( MazeType &maze ) //打印结果
{
int count = 0;
int 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++;
}
}
/* 2. 迷宫实现如上 */
//3. 方向实现如下
void InitMoveDirection( MoveDirection &MD ) //North=0,South=1,West=2,East=3
{
int k;
for( k = 0;k <= 2;k++ )
{
MD[ k ].next = k+1;
}
MD[ 3 ].next = 0;
}
int Transform( int Gone ) //Gone表示来的方向
{ //函数的功能是返回与Gone相反的方向
if( Gone%2 == 0 ) return Gone+1;
else return Gone-1;
}
//3. 方向实现如上
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;
}
}
int main()
{
int key;
Stack s;
MoveDirection MD[ 4 ];
MazeType maze[ M*N ];
InitMoveDirection( MD );
InitMaze( maze );
printf( "Maze Below:\n" );
Print( maze );
key = MazeSolve( maze, s, MD );
if( ! key )
{
printf( "No Path" );
}
else
{
printf( "Maze Sovled Below:\n" );
Print( maze );
}
system("pause");
return 0;
}
