迷宫求解.cpp

迷宫求解。数据结构科重要程序。通过C语言实现。能正常运行。但需要帐户才能下载。请见谅。

#include<stdio.h>
#define MAXSIZE 10
int top=0;
int stack[MAXSIZE*MAXSIZE][2];
Find_Path(int maze[MAXSIZE][MAXSIZE],int rx,int ry,int cx,int cy)
{
 int leap=0;
 stack[top][0]=rx;
 stack[top][1]=ry; 
 while(1)
 { 
   leap=0;
   if(maze[rx][ry+1]==0)  //向东
   {ry++;leap=1;}
   else if(maze[rx+1][ry]==0) //向南
   {rx++;leap=1;}
   else if(maze[rx][ry-1]==0) //向西
   {ry--;leap=1;}
   else if(maze[rx-1][ry]==0) //向北
   {rx--;leap=1;}
   if(!leap)
   {
	 maze[stack[top][0]][stack[top][1]]=5;  //返回时记录
     top--;
     if(top==0)
	 {
		printf("迷宫无出路\n");
        return 0;
	 }
     rx=stack[top][0];
	 ry=stack[top][1];
   }
   else
   {
     maze[rx][ry]=2;
     top++;
     stack[top][0]=rx;
     stack[top][1]=ry;
     if(rx==cx&&ry==cy)
	   return 1;
   }
 }
}


void main()
{
 int i,j,result;
 int m,n,m1,n1,k;
 int maze[MAXSIZE][MAXSIZE]=
 {
  1,1,1,1,1,1,1,1,1,1,
  1,0,0,1,0,0,0,1,0,1,
  1,0,0,1,0,0,0,1,0,1,
  1,0,0,0,0,1,1,0,0,1,
  1,0,1,1,1,0,0,0,0,1,
  1,0,0,0,1,0,0,0,0,1,
  1,0,1,0,0,0,1,0,0,1,
  1,0,1,1,1,0,1,1,0,1,
  1,1,0,0,0,0,0,0,0,1,
  1,1,1,1,1,1,1,1,1,1};
  printf("我是Tina～\n");
  printf("生成的地图为:\n");
  for(i=0;i<10;i++)
  {
	for(j=0;j<10;j++)
	{
	 if(maze[i][j]==1)	 
		  printf("@");
	 else
		 printf("-");
	}
	printf("\n");
  }

  printf("@符号表示墙\n");
  printf("-符号表示空间\n");
  printf("请输入入口坐标\n");
while(1)
{
  printf("请输入入口的横坐标:");
  while(1)
  {
   
   scanf("%d",&m);
   if(m>MAXSIZE)
	  printf("输入超出范围,请重新输入\n");
   else
     break;
  }
  while(1)
  {
   printf("请输入入口的竖坐标:");
   scanf("%d",&n);
   if(n>MAXSIZE)
	  printf("输入超出范围,请重新输入\n");
   else
     break;
  }
  if(maze[m][n]==0)
	  break;
  else
	  printf("输入错误,请重新输入!\n");
}
 while(1)
 {
  printf("请输入出口的坐标:\n");
  while(1)
  {
   printf("请输入入口的横坐标:");
   scanf("%d",&m1);
   if(m1>MAXSIZE)
	  printf("输入超出范围,请重新输入\n");
   else
     break;
  }
  while(1)
  {
   printf("请输入出口的竖坐标");
   scanf("%d",&n1);
   if(n1>MAXSIZE)
	  printf("输入超出范围,请重新输入\n");
   else
     break;
  }
  if(maze[m1][n1]==0)
	  break;
  else
	  printf("输入错误,请重新输入!\n");
 }
 result=Find_Path(maze,m,n,m1,n1);
 printf("路径为:\n");
 for(i=0;i<top;i++) 
 { 
  printf("(%d,%d)-->",stack[i][0],stack[i][1]); 
  if((i+1)%5==0) 
  printf("\n"); 
 } 
 printf("(%d,%d)\n",m1,n1);
 maze[m][n]=3;
 maze[m1][n1]=4;
  for(i=0;i<MAXSIZE;i++)
  {
	  for(j=0;j<MAXSIZE;j++)
	  {
		if(maze[i][j]==0||maze[i][j]==5)
			printf("-");
		else if(maze[i][j]==1)
			printf("@");
		else if(maze[i][j]==2)
	        printf(".");
		else if(maze[i][j]==3)
			printf("&");
		else 
			printf("#");
	  }
	  printf("\n");
  }
  printf("@符号表示墙\n");
  printf("-符号表示空间\n");
  printf("&符号表示入口\n");
  printf("#符号表示出口\n");
  printf(".符号表示路径\n");
 return;
}