迷宫问题 maze 迷宫算法的实现

迷宫问题是比较经典的算法设计题，改C程序较好的实现了迷宫问题。

#include 
#include 
#include
#include
#define M 120
#define N 120
#define MAXLEN M*N
int sxsyexey;
int nm;
char maze[M][N];
double BeginTimeconsumeFinish;//时间消耗
 
 

typedef struct//栈元素类型
{   int xydir;
}elemtype;

typedef struct//栈结构
{  elemtype stack[MAXLEN];
   int top;
} sqstack;

 typedef struct//队列元素类型
{   int xypre;
    
}QueueNode;

typedef struct//队列结构
{   QueueNode queue[MAXLEN];
    int front rear;
}SqQueue; 

struct moved//方向数组结构体类型
{   int dxdy;
};


void inimove（struct moved move[]）//初始化方向数组
{    move[0].dx=0;move[0].dy=1;
     move[1].dx=1;move[1].dy=0;
     move[2].dx=0;move[2].dy=-1;
	 move[3].dx=-1;move[3].dy=0;
}


void inistack（sqstack *s）//初始化栈
{    s->top=-1;

}

int push（sqstack *selemtype x）//入栈操作
{   if（s->top==MAXLEN-1）
        return 0;
    else
	{    s->stack[++s->top]=x;
	     return 1;
	}
}

elemtype pop（sqstack *s）//出栈操作
{elemtype elem;
    if（s->top<0）
	{   elem.x=NULL;
        elem.y=NULL;
	    elem.dir=NULL;
	    return elem;
	}
    else 
	{   s->top--;
        return（s->stack[s->top+1]）;
	}
}


void iniqueue（SqQueue *s）
{    s->front=1;
     s->rear=1;
}


int shortpath（char maze[][N]struct moved move[]SqQueue *p）//寻找最段路径 
{    int ijxydir;
     p->queue[1].x=sx;
     p->queue[1].y=sy;
	 p->queue[1].pre=0;
	 maze[sx][sy]=-1;
	 while（p->front<=p->rear）
	 {    i=p->queue[p->front].x;//ij为出发点
	      j=p->queue[p->front].y; 
	      for（dir=0;dir<4;dir++）//寻找从ij出发四个方向有那些可以到达
		  {    x=i+move[dir].dx;
		       y=j+move[dir].dy;
		       if（maze[x][y]==‘O‘）// 如有可到达点将此点入队
			   {   p->rear++;
			       p->queue[p->rear].x=x;
				   p->queue[p->rear].y=y;
				   p->queue[p->rear].pre=p->front;
				   maze[x][y]=-1;
			   }
			   if（（x==ex）&&（y==ey））//如到达出口返回真
			      return 1;
		  }
	      p->front++;//对头指针指向下一队列元素
	}
	return 0;
}


void printpath（SqQueue *psqstack *s）//将最短路径入栈
{    int if;
     elemtype elem;
	 i=p->front;
	 do//从队列中取出最短迷宫路经放入栈中
	 {   elem.x=p->queue[i].x;
         elem.y=p->queue[i].y;
		 f=push（selem）;
		  if（f==0）
		     printf（“栈长度太短\n“）;
		  i=p->queue[i].pre;
		   	 
	}while（i>0）;//不变了
	printf（“\n“）;
}


void draw（char maze[][N]sqstack *s）//将路径从栈中弹出还原为原来的并以P代O
{    int ij;
     elemtype elem;
	 for（i=1;i<=M;i++）
	      for（j=1;j<=N;j++）
		   if（maze[i][j]==-1）
				 maze[i][j]=‘O‘;
	 while（s->top>-1）
	 {   elem=pop（s）;
	     i=elem.x;
		 j=elem.y;
		 maze[i][j]=‘P‘;
	  } 
	maze[sx][sy]=‘S‘;
	for（i=1;i<=m;i++）//输出找到路径后的迷宫
	{for（j=1;j<=n;j++）
		{printf（“%c“maze[i][j]）;
        }
	    printf（“\n“）;
	}
}
	

int main（）
{
	FILE *fp;
	char filename[10];
	int ijf;
    sqstack *s;
	SqQueue *p;
    printf（“Please input the file name:“）;
	scanf（“%s“filename）;
	
	fp=fopen（filename“r“）;
	if（fp==NULL）
   	{	printf（“打开失败“）;
	    exit（1）;
	}
	fscanf（fp“%d“&m）;
	fscanf（fp“%d“

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       2608  2007-11-29 16:03  maze.txt

     文件       4293  2007-12-05 09:24  maze.cpp

     文件     217146  2007-11-29 16:05  maze.exe

----------- ---------  ---------- -----  ----

               224047                    3