迷宫问题求解(C++非递归程序)

时间:2024-11-11 10:18:23
 else           //Choose=2  ,输入迷宫
 {
  cout<<"请输入迷宫的长和宽:";
  int a,b;
  cin>>a>>b;             //输入迷宫的长和宽
  cout<<"请输入迷宫内容:/n";
  m=a;
  n=b;          //m,n分别代表迷宫的行数和列数
  maze=new int *[m+2];  //申请长度等于行数加2的二级指针
  for(i= 0;i<m+2;i++)  //申请每个二维指针的空间
  {
   maze[i]=new int[n+2];
  }
  for(i=1;i<=m;i++)          //输入迷宫的内容,1代表可通,0代表不通
   for(j=1;j<=n;j++)
    cin>>maze[i][j];
  cout<<"是否保存新迷宫?/n";
  char choose;
  cin>>choose;
  if(choose=='Y'||choose=='y')
  {
   char ch;
   ofstream fop("");    
   for(i=1;i<=m;i++)
   {
    for(j=1;j<=n;j++)
    {
     ch='0'+maze[i][j];
     fop<<ch;
    }
    fop<<endl;
    flush(cout);
   }
   ();
  }
 }
//给迷宫的四周加一堵墙,即把迷宫四周定义为1
 for(i=0;i<m+2;i++)             
  maze[i][0]=maze[i][n+1]=1;
 for(i=0;i<n+2;i++)
  maze[0][i]=maze[m+1][i]=1;
 return maze;              //返回存贮迷宫的二维指针maze
}
bool Mazepath(int **maze,int m,int n)
          //寻找迷宫maze中从(0,0)到(m,n)的路径
           //到则返回true,否则返回false
{
 stack q,p;       //定义栈p、q,分别存探索迷宫的过程和存储路径
 DataType Temp1,Temp2;     
 int x,y,loop;
 =1;
 =1;
 (Temp1);           //将入口位置入栈
 (Temp1);
 maze[1][1]=-1;          //标志入口位置已到达过
 while(!())      //栈q非空,则反复探索
 {
  Temp2=();      //获取栈顶元素
  if(!(().x==().x&&().y==().y))
   (Temp2);        
     //如果有新位置入栈,则把上一个探索的位置存入栈p
  for(loop=0;loop<4;loop++)   //探索当前位置的4个相邻位置
  {
   x=+move[loop].x;     //计算出新位置x位置值
   y=+move[loop].y;      //计算出新位置y位置值
   if(maze[x][y]==0)         //判断新位置是否可达
   {
    =x;
    =y;
    maze[x][y]=-1;          //标志新位置已到达过
    (Temp1);         //新位置入栈
   }
   if((x==(m))&&(y==(n)))    //成功到达出口
   {
    =m;
    =n;
    =0;
    (Temp1);       //把最后一个位置入栈
    PrintPath(p);        //输出路径
    Restore(maze,m,n);        //恢复路径
    return 1;            //表示成功找到路径
   }
  }
  if(().x==().x&&().y==().y)
        //如果没有新位置入栈,则返回到上一个位置
  {
   ();
   ();
  }
 }
 return 0;           //表示查找失败,即迷宫无路经
}
void PrintPath(stack p)        //输出路径
{
 cout<<"迷宫的路径为/n";
 cout<<"括号内的内容分别表示为(行坐标,列坐标,数字化方向,方向)/n";
 stack t;            //定义一个栈,按从入口到出口存取路径
 int a,b;
 DataType data;
 LinkNode *temp;
 temp=new LinkNode;         //申请空间
 temp->data=();        //取栈p的顶点元素,即第一个位置
 (temp->data);  //第一个位置入栈t
 delete temp;         //释放空间
 while(!())    //栈p非空,则反复转移
 {
  temp=new LinkNode;
  temp->data=();         //获取下一个位置
  //得到行走方向
  a=().x-temp->;   //行坐标方向
  b=().y-temp->;   //列坐标方向
  if(a==1) temp->=1;     //方向向下,用1表示
  else if(b==1) temp->=2; //方向向右,用2表示
  else if(a==-1) temp->=3;  //方向向上,用3表示
  else if(b==-1) temp->=4;  //方向向左,用4表示
  (temp->data);            //把新位置入栈
  delete temp;
 }
 //输出路径,包括行坐标,列坐标,下一个位置方向
 while(!())         //栈非空,继续输出
 {
  data=();
  cout<<'('<<<<','<<<<','<<<<",";  //输出行坐标,列坐标
  switch()   //输出相应的方向
  {
  case 1:cout<<"↓)/n";break;
  case 2:cout<<"→)/n";break;
  case 3:cout<<"↑)/n";break;
  case 4:cout<<"←)/n";break;
  case 0:cout<<")/n";break;
  }
 }
}
void Restore(int **maze,int m,int n)       //恢复迷宫
{
 int i,j;
 for(i=0;i<m+2;i++)            //遍历指针
  for(j=0;j<n+2;j++)      
  {
   if(maze[i][j]==-1)         //恢复探索过位置,即把-1恢复为0
    maze[i][j]=0;
  }
}
四、调试分析
1、由于对迷宫路径探索的算法和二维指针的推敲不足,使程序调试时费时不少
2、本程序有些代码重复出现,从而减少了空间的利用率和增加了程序代码的杂乱性
3、本程序模块划分比较合理,且利用指针存储迷宫,操作方便。
4、算法的时空分析
    该算法的运行时间和使用系统栈所占有的存储空间与迷宫的大小成正比,在最好情况下的时间和空间复杂度均为O(m+n),在最差情况下均为O(m*n),平均情况在它们之间
5、本实验采用数据抽象的程序设计方法,将程序分为3个模块,使得设计时思路清晰,实现时调试可以顺利完成,各模块具有较好的可重用性,确实得到了一次良好的程序设计训练。
五、用户手册
1、本程序的运行环境为DOS操作系统
2、进入演示程序后即显示文本方式的用户界面
 
 
3、进入界面后,就会提示输入字符串的输入形式,结束符为“回车符”。
六、测试结果
    如上图所示。
七、附录
源程序文件名清单:
                    //元素结点定义单元
                  //链表实现单元
                          //主程序