main.cpp

迷宫问题

/////////////////////////////////////////////////////////////////////
/*
  Name:   main.cpp 
  Author:  罗丹 
  Description: 主函数文件   
*/

#include"stack.h"
#include<iostream>
#include<string>
#include<fstream>
using namespace std ;

/*
   Description: 外部函数的声明部分

*/
bool findpath(int **maze,int m,int n);               //寻找迷宫路径     
void PrintPath(stack p);                             //输出路径
void Restore(int **maze,int m,int n);                //恢复迷宫
Move move[4]={{0,1},{1,0},{0,-1},{-1,0}};            //定义当前位置移动的4个方向(上，右，下，左)
int** readFile (int &m,int &n);
int** writeFile(int &m,int &n);
/*
  Description:  main.cpp
*/
                           
void main()
{ 
   cout<<endl;
   cout<<"◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆"<<endl;
   cout<<"        2007-2008年度第一学期数据结构课程之课程设计            "<<endl;
   cout<<endl;
   cout<<"                                    ——迷宫问题                 "<<endl; 
   cout<<"  开发员 : 罗丹"<<endl;
   cout<<"  专业班级: 计算机061班"<<endl;
   cout<<"◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆"<<endl;
   cout<<"                    欢迎进入迷宫游戏          "<<endl;
  int m=0,n=0;       
  int **maze;  
  char ch;
  int flag=0,flag1=0; 
  while(flag1==0)
  {
  while(flag==0)//标志是否重新选择
  {cout<<endl;
   cout<<"  ★请从以下选项中选择获取迷宫的方法！"<<endl;
   cout<<"        <a>从文件中读取"<<endl;
   cout<<"        <b>直接自行输入"<<endl;
   cout<<"  ★请选择:";
      cin>>ch;
      if(ch=='a'){maze=readFile(m,n);flag=1;}
      else if(ch=='b'){maze=writeFile(m,n);flag=1;}
      else 
   cout<<"  ★ Sorry!您输入的选择代码不在范围内!请从新选择"<<endl;
       
  }

  if(findpath(maze,m,n))  
  cout<<"  ★ Congratulations! 迷宫路径探索成功!"<<endl; //得到路径
  else 
  cout<<"  ★Sorry! 路径不存在★"<<endl;
  cout<<endl;
  cout<<"  ★ 继续玩吗？(y/n)";  
  char c;
  cin>>c;
  if(c==n) flag1=1;
  else flag=0;
  }
   cout<<"◆◆◆◆◆◆◆ 谢谢,您已经退出迷宫系统  ◆◆◆◆◆◆◆"<<endl;
   cout<<"◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆"<<endl;
}

/*
  Description:  获取迷宫函数
*/

int** readFile (int &m,int &n)                     //读出文件
{int **maze;              
 int i=0,j=0;
 cout<<"  ★您选择的是直接从文件中读取迷宫!"<<endl;
 cout<<endl;
 cout<<"        文件中的迷宫如下：   "<<endl;
 char ch;                                          //定义一个字符，读取文件中的内容
 ifstream open("maze.txt");                        //定义一个文件对象，并打开文件"maze.txt"
  //读取内容记录行数和列数
 while(open.get(ch))                               //从读取文件中内容（一旦个字符形式）
  {if(ch=='0'||ch=='1')   
       {j++; }                                //是‘0’或‘1’字符宽就加1
   if(ch=='\n')        
   {
	i++;                                           //如果是换行符，就行加1
    n=j;                                           //得列数
    j=0;   
   }
  }
  open.close();                                    //读取文件结束
  m=i;            
  maze=new int *[m+2];                             //申请长度等于行数加2的二维指针(为后面的回复迷宫打下基础)
  for(i= 0;i<m+2;i++)                              //申请空间
  {maze[i]=new int[n+2];}
  i=j=1;
  ifstream open1("maze.txt");                      //重新读取文件，以得到内容
  while(open1.get(ch))
  {
   if(ch=='1'||ch=='0')
   {maze[i][j]=ch-'0';                             //把数字字符转化为数字，并存到指针里
    cout<<maze[i][j]<<"   ";                       //在屏幕中显示迷宫
    j++;}
   if(ch=='\n')                                    //遇到换行，指针也相应换行
   {cout<<endl;
    i++;
    j=1;}
  }
   open1.close();                                  //读取结束
   return maze; 
}

int** writeFile (int &m,int &n)                     //将自定义迷宫写入文件
{int a,b; 
int i,j;
int**maze;
 cout<<"  ★您选择的是自行输入迷宫!"<<endl;
 cout<<"    请输入迷宫的长:";cin>>b;                  //输入迷宫的长和宽
 cout<<"    请输入迷宫的宽:";cin>>a;     
 cout<<"  ★请输入迷宫内容(0代表可通，1代表不通):\n";
  m=a;
  n=b;                                              //m,n分别代表迷宫的行数和列数
  maze=new int *[m+2];  
  for(i= 0;i<m+2;i++) 
  {maze[i]=new int[n+2];}   //创新点:随意申请空间
  for(i=1;i<=m;i++)                                //输入迷宫的内容，0代表可通，1代表不通
   for(j=1;j<=n;j++)
    cin>>maze[i][j];
  cout<<"  ★是否保存新迷宫？(y/n): ";
  char choose;
  cin>>choose;
  if(choose=='Y'||choose=='y')
  {char ch;
  string str;
  cout<<"  ★请输入保存迷宫的文件名(以.txt结束):";
  cin>>str; 
  ofstream open(str.c_str());                      //创新点：随意创建存储迷宫的文件
   for(i=1;i<=m;i++)
   {for(j=1;j<=n;j++)
    {ch='0'+maze[i][j];
     open<<ch;}
    open<<endl;
    flush(cout);}
   open.close();}
   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;
 } 

/*
  Description:  探索路径函数
*/
bool findpath(int **maze,int m,int n)
{stack q,p;                                      //定义栈p、q,分别存探索迷宫的过程和存储路径
 DataType Temp1,Temp2;      
 int x,y,loop;
 Temp1.x=1;
 Temp1.y=1;
 q.Push(Temp1);                                   //将入口位置入栈
 p.Push(Temp1);
 maze[1][1]=-1;                                  //标志入口位置已到达过
 while(!q.IsEmpty())                             //栈q非空，则反复探索
 {Temp2=q.GetPop();      
  if(!(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)) 
   p.Push(Temp2);         
   //如果有新位置入栈，则把上一个探索的位置存入栈p
  for(loop=0;loop<4;loop++)                     //探索当前位置的4个相邻位置
  {x=Temp2.x+move[loop].x;     
   y=Temp2.y+move[loop].y;      
   if(maze[x][y]==0)                            //判断新位置是否可达
   {Temp1.x=x;
    Temp1.y=y;
    maze[x][y]=-1;                              //标志新位置已到达过
    q.Push(Temp1);  }                           //新位置入栈
   if((x==(m))&&(y==(n)))                       //成功到达出口
   {Temp1.x=m;
    Temp1.y=n;
    Temp1.pre=0;
    p.Push(Temp1);                              //把最后一个位置入栈
    PrintPath(p);        
    Restore(maze,m,n);                          //恢复路径（因为迷宫里面的内容已被改变
    return 1; }}                               //表示成功找到路径  
if(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)//如果没有新位置入栈，则返回到上一个位置       
{p.Pop();
 q.Pop();}}
 return 0;                                     //表示查找失败，即迷宫无路经
}

/*
  Description:  输出路径函数
*/

void PrintPath(stack p)                        //输出路径
{cout<<endl;
 cout<<"  ★★迷宫的路径为"<<endl;
 cout<<"      说明:括号内的内容分别表示为(行坐标,列坐标,方向)\n";
 stack t;                                      //定义一个栈，按从入口到出口存取路径
 int row,column;
 DataType data;
 Node *temp;
 temp=new Node;                               //申请空间
 temp->data=p.Pop();        
 t.Push(temp->data);                          //第一个位置入栈
 delete temp;         
 while(!p.IsEmpty())                          //栈p非空，则转移
 {temp=new Node;
  temp->data=p.Pop();                         //获取下一个位置
  //得到行走方向
  row=t.GetPop().x-temp->data.x;               //行坐标方向
  column=t.GetPop().y-temp->data.y;           //列坐标方向
  if(row==1) temp->data.pre=1;                //向下，用1表示
  else if(column==1) temp->data.pre=2;        //向右，用2表示
  else if(row==-1) temp->data.pre=3;          //向上，用3表示
  else if(column==-1) temp->data.pre=4;       //向左，用4表示
  t.Push(temp->data);                         //把新位置入栈
  delete temp;
 }
 while(!t.IsEmpty())                          //栈非空，继续输出
 {data=t.Pop();
  cout<<"         "<<'('<<data.x<<','<<data.y<<",";  
  switch(data.pre)                            //输出相应的方向 
  {case 0:cout<<")\n";break;
   case 1:cout<<"向下)\n";break;
   case 2:cout<<"向右)\n";break;
   case 3:cout<<"向上)\n";break;
   case 4:cout<<"向左)\n";break;
   }}}

/*
  Description:  恢复路径函数
*/

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;}
}