迷宫3.txt

是软件技术数据结构方向的现成的课程设计

//数据结构老师布置了上机作业:迷宫问题.我用了一天多的时间完成.程序如下:

   //语言C++;平台:Visual C++


//迷宫问题
//核心算法描述：用穷举法，按东南西北的方向一步步试探，路不通便退回。
//具体设计思路：采用栈index记录行走的路径；用栈direction记录了对每一个位置下面要走的方向；
//用三维数组p记录了对每一个位置的四个方向是否可走；
//如果此时已处在某一个位置，下面判断接下来要走的方向，此方向必须满足以下三个条件：
//1.这个方向不是上一步过来的方向；
//2.这个方向在不是以前已试探过的走不通的方向；
//3.如果按这个方向走，下一个位置前面的路径中没有走过；
//如果满足以上三个条件，再判断下一个位置是否有障碍，有，则继续找另外的方向；没有，则此方向和下一个位置入栈。
//如果四个方向均不满足上述条件，则此位置出栈，并记录上一个方向不可行。
#include<stack>
#include<iostream>
using namespace std;
int main()
{
stack<int> index;//此栈记录了行走的路径的位置
stack<int> direction;//此栈记录了对每一个位置下面要走的方向（1：右；2：下；3：左；4：上）
     int p[10][10][5]={0};//此三维数组记录了对每一个位置的四个方向是否可走（1：不可走）
int x=1;//迷宫的横坐标
int y=1;//迷宫的纵坐标
int isgo;//计量变量
int x1,y1;//x,y的临时存储变量
int bef_d;//对前一个方向的判断
int copy[100][2]={0};//二维数组，作为index的同步存储器，可实现一些查询操作
int lenth=0;//记录所走的路径数,也即数组长度
int isdouble=0;//计量所走路径是否与以前重复的变量
     index.push(11);
     int a[10][10]={1,1,1,1,1,1,1,1,1,1,
              1,0,1,0,0,0,1,1,1,1,
              1,0,0,0,1,0,0,0,0,1,
           1,1,0,1,1,1,1,0,0,1,
           1,0,0,0,1,0,1,1,0,1,
           1,1,0,1,0,0,1,0,0,1,
           1,0,0,0,1,0,1,0,1,1,
           1,0,1,0,0,0,1,0,0,1,
           1,0,0,1,0,1,0,1,0,1,
           1,1,1,1,1,1,1,1,1,1};//用二维数组表示迷宫；此数组可变，但必须能走通。

while(!((x==8)&&(y==8))){
   isgo=0;
   for(int i=1;i<5;i++){
    if(direction.empty())bef_d=0;
    else{
     switch(direction.top()){
        case 1:bef_d=3;break;
        case 2:bef_d=4;break;
        case 3:bef_d=1;break;
        case 4:bef_d=2;break;
     }
    }
    if((i!=bef_d)&&(p[x][y][i]!=1)){//头注释中的条件1，2
     switch(i){
     case 1:{x1=x;y1=(y+1);}break;
     case 2:{y1=y;x1=(x+1);}break;
     case 3:{x1=x;y1=(y-1);}break;
     case 4:{y1=y;x1=(x-1);}break;}
     isdouble=0;
     for(int b=1;b<=lenth;b++){
      if((x1==copy[b][0])&&(y1==copy[b][1]))
       isdouble++;
     }
     if(isdouble>=1)continue;//头注释中的条件3
     else{
      if(a[x1][y1]==0){
       index.push(x1*10+y1);
          copy[++lenth][0]=x1;
          copy[lenth][1]=y1;
          direction.push(i);
          isgo=1;
          x=x1;
          y=y1;
      }
     }
    }
    if(isgo==1)break;
   }
   if(isgo==0){
       index.pop();
    lenth--;
    x=(index.top ()/10);
    y=(index.top ()%10);
    p[x][y][direction.top()]=1;
    direction.pop();
   }
}
cout<<"迷宫为："<<endl;
int k=0;
for(int i=0;i<=9;i++)   //输出迷宫。
   for(int j=0;j<=9;j++){
             cout<<a[i][j]<<",";
       k++;
    if(k%10==0)
     cout<<endl;
   }
cout<<endl;
cout<<"此迷宫的一条通路是："<<endl;
cout<<"(注意按从后往前的顺序。每个数十位是x坐标，个位是y坐标。)"<<endl;

k=0;
while(!index.empty()){       //输出函数。
   cout<<index.top()<<"   ";
   index.pop();
   k++;
   if(k%10==0)
    cout<<endl;
}

cout<<'\n'<<'\n'<<'\n'<<"                                           程序编写人"<<endl;
cout<<"                                              荣辉"<<endl;
cout<<"                                            13051195"<<endl;

return 0;
}