迷宫求解完.cpp

数据结构中重要的迷宫算法

#include<iostream>
#include<stack>
#include<malloc.h>
using namespace std;
struct SHAGUO
{
 int x;
 int y; 
};
int **array;
int outx=0,outy=0;//出口坐标
stack<SHAGUO>shaguo;
void Creat(int sum)
{
 int i,j;
 array=(int **)malloc((sum+2)*sizeof(int *));
 for( i=0;i<=sum+1;i++)
  array[i]=(int *)malloc((sum+2)*sizeof(int));
 i=0;/*下面把迷宫四周设成墙   ,0 代表墙，1代表路*/
 for(j=0;j<=sum+1;j++)
 {
  array[i][j]=0;
  array[j][i]=0;
 }
 i=sum+1;
 for(j=0;j<=sum+1;j++)
 {
  array[i][j]=0;
  array[j][i]=0;
 }
 cout<<"请输入迷宫，0代表墙，1代表路,3代表出口,入口默认为(1,1)"<<endl;
 
 for(i=1;i<=sum;i++)
  for(j=1;j<=sum;j++)
   cin>>array[i][j];   
 for(i=1;i<=sum;i++)
  for(j=1;j<=sum;j++)
  {
   if(array[i][j]==3)
   {
    outx=i;
    outy=j;
   }
  }
  if(!(outx||outy))
  {
   cout<<"没有出口!程序将采用默认出口( "<<sum<<" , "<<sum<<" )"<<endl;
   outx=sum;
   outy=sum;
   array[sum][sum]=1;

  }
}
void ok(int num)
{
 cout<<endl<<"走出来啦!"<<endl;
 SHAGUO shaguo1;
 int x,y;
 while(!shaguo.empty())
 {
  shaguo1=shaguo.top();
  x=shaguo1.x;
  y=shaguo1.y;
  array[x][y]=4;
  shaguo.pop();
 }
 array[outx][outy]=4;
 for(x=1;x<=num;x++)
 {
  for(y=1;y<=num;y++)
  {
      if(array[x][y]==4)
    cout<<'\1'<<' ';
   else cout<<'*'<<' ';
  }

   cout<<endl;
 }
 system("pause");
 exit(0);
}
void bad()
{
 cout<<endl<<"没有路!"<<endl;
 system("pause");
 exit(0);
}
void go(int num)
{
 SHAGUO shaguo2,shaguo1;
 shaguo2.x=1;
 shaguo2.y=1;
 shaguo.push(shaguo2);
 int X=1,Y=1;
 int come=1;//探索方向
 while(1&&!shaguo.empty())
 {
  shaguo1=shaguo.top();
  X=shaguo1.x;
  Y=shaguo1.y;
  switch(come)
  {
  
  case 1://向下
   {
    
    X=X+1;
    if(array[X][Y]&&array[X][Y]!=2)//不是走下面上来的
    {
     if(X==outx&&Y==outy)
      ok(num);
     shaguo2.x=X;
     shaguo2.y=Y;
     array[X][Y]=2;
     shaguo.push(shaguo2);
     come=1;
    }
    else 
    {
     come++;
    }
  
   }break;
  case 2://向右
   {
    Y=Y+1;
    if(array[X][Y]&&array[X][Y]!=2)
    {
     if(X==outx&&Y==outy)
      ok(num);
     shaguo2.x=X;
     shaguo2.y=Y;
     shaguo.push(shaguo2);
     array[X][Y]=2;
     come=1;
     
    }
    else
    {    
     come++;
    }
   }break;
  case 3:
   {
    X=X-1;
    if(array[X][Y]&&array[X][Y]!=2)
    {
     if(X==outx&&Y==outy)
      ok(num);
     shaguo2.x=X;
     shaguo2.y=Y;
     shaguo.push(shaguo2);
     array[X][Y]=2;
     come=1;
    }
    else
    {
     come++;
    }
   }break;
   case 4://向右
   {
    Y=Y-1;
    if(array[X][Y]&&array[X][Y]!=2)
    {
     if(X==outx&&Y==outy)
      ok(num);
     shaguo2.x=X;
     shaguo2.y=Y;
     shaguo.push(shaguo2);
     array[X][Y]=2;
     come=1;
    }
    else
    {
     come=1;
     array[X][Y]=0;
     shaguo.pop();
     if(!shaguo.empty())
     {
        shaguo1=shaguo.top();
        if(shaguo1.x==1&&shaguo1.y==1)
      bad();
     }
     else bad();
    }

   }break;
  }
 }
 bad();

}
void main()
{ 
 cout<<"请输入迷宫大小，只需输入迷宫的维数，8即是8*8的迷宫"<<endl;
 int sum;
 cin>>sum;  
 Creat(sum);
    go(sum);
}