迷宫.c

随机产生一个迷宫。可以找出一条可以通过的路径。也可以找出全部可以通过的路径。

/*迷宫问题*/
/*03计算机3班 2003374313 李南宁*/
#include <stdlib.h> 
#include <stdio.h> 
#include <time.h>
long id;
int maze[1000][1000],maze2[1000][1000],m,n,s,choose=1;    /*初始化全局变量*/
int a[8]={0,1,1,1,0,-1,-1,-1};           /*x坐标在八个方向上的增量*/
int b[8]={-1,-1,0,1,1,1,0,-1};           /*y坐标在八个方向上的增量*/
struct node{                             /*顺序存放可达路径的坐标*/
	int x;
	int y;}
index[100];
initialmaze()                          /*初始化随机地图*/
{
int i,j; 
for(i=0;i<100;i++)
for(j=0;j<100;j++)
maze2[i][j]=1;
srand((unsigned)time(NULL));          
for(i=1; i<=m; i++) 
for(j=1;j<=n;j++)
if( rand()*10/RAND_MAX>=4) maze2[i][j]=0;   /*产生10个随机数,把对于如果随机数大于4，对应的迷宫
                                               方块设为0，反之设为1，可以达到相对的随机！*/

else maze2[i][j]=1; 
maze2[1][1]=0;
maze2[m][n]=0;
} 


int way2(int locx,int locy)                          /*输出所有路径的函数*/
{

	int i;
	if(maze[m][n]==2) {output();id++;/*return 1;*/}   /*关键是把return去掉，让函数一直执行下去*/
	else if(maze[locy][locx]==0)
	{
		maze[locy][locx]=2;
		index[s].x=locy;index[s++].y=locx;         /*顺序记录可达方块的坐标值*/
		for(i=0;i<8;i++)                       
		{(way2(locx+a[i],locy+b[i]));             /*递归*/
		if(maze[m][n]==2) break;
		}
maze[locy][locx]=0;s--;                                /*回朔*/
}
}

int way1(int locx,int locy)                         /*产生一条路径的函数*/
{

	int i;
	if(maze[m][n]==2) {output();id++;return 1;}      /*一旦找到一条就跳出*/
	else if(maze[locy][locx]==0)
	{
		maze[locy][locx]=2;
		index[s].x=locy;index[s++].y=locx;
		for(i=0;i<8;i++)
		if(way1(locx+a[i],locy+b[i]))
        return 1;
maze[locy][locx]=3;
	return 0;
}
else return 0;
}
output()                                                 /*输出函数*/
{
	int i,j,t=0;
	if(choose==1) printf("其中一条路径:");
	else  printf("第%d条路径:",id+1);
	for(i=0;i<s-1;i++)
	{	printf("(%d,%d)->",index[i].x,index[i].y);
     	/*if(i)
		if(!(i%10)) printf("\n");*/} 
	printf("(%d,%d)",m,n);
  printf("\n\n");
}

main()                                          /*主函数*/
{
	int i,j;
	
	printf("***************迷宫问题***************\n");
	while(1)
	{
		s=0;
    printf("随机产生一个迷宫(1表示围墙，0表示可达)\n");
	printf("所输入的数据不要超过1000\n");
loop:	printf("请输入迷宫的宽:");                      /*初始化迷宫的大小*/
		scanf("%d",&m);
printf("            长:");
		scanf("%d",&n);initialmaze();
		for(i=0;i<=m+1;i++)
		{	for(j=0;j<=n+1;j++)
				printf("%d ",maze2[i][j]);
		printf("\n");}
while(1)
{	 s=0;  
	for(i=0;i<=m+1;i++)
			for(j=0;j<=n+1;j++)
		maze[i][j]=maze2[i][j];
	printf("1 找出一条路径\n");                                /*选单*/
	printf("2 找出全部路径(长宽应该小于5，否则超过计算机运算能力)\n");
	printf("3 重新产生随机地图\n");
	printf("4 退出!\n");
	printf("请选择:");
	scanf("%d",&choose);
   switch(choose)
   {
   case 1:id=0;way1(1,1);if(id==0) printf("该迷宫没出口!\n\n\n");break;		
   case 2:id=0;way2(1,1);if(id==0)printf("该迷宫没出口!\n\n\n");break;
   case 3:goto loop;break;
   case 4: return ;
   }
   }
   }
}