新建 文本文档.txt

迷宫问题的代码

///////////////作者：刘志磊/////////////////////// 
///////////////时间：2007.4.11.10.10///////////// 
#include<iostream> 
using namespace std; 
//#include<process.h> 
#include <stdio.h> 
#include<time.h> 
#define TIMEMAX 6000 
#define OK 0 
#define ERROR -1 
#define UP 1   //用于存储方向的常量 
#define DOWN 2 
#define LEFT 3 
#define RIGHT 4 
char a[15][60]; //定义存储迷宫用的字符型二维数组   
/*定义存储走过路线的栈*/ 
typedef struct SNode 
 { 
   int data; 
   struct SNode *next; 
  }SNode; 
typedef struct 
{ 
   int length; 
   SNode *top; 
}STACK;/*显示迷宫函数*/ 
void ShowMaze() 
{ 
   int i,j; 
   char c=2; 
   system("cls.exe");  
   system("color 0f"); 
   cout<<"\t\t\t\t迷宫问题"<<"\n\n\n";  
   for(i=0;i<15;i++) 
   { 
     cout<<"\t"<<c; 
     for(j=0;j<60;j++) 
     cout<<a[i][j]; 
     cout<<c<<"\n"; 
   } 
} 
/*迷宫初始化函数*/ 
void InitMaze() 
{ 
int n,i,j; 
for(i=0;i<15;i++) 
  for(j=0;j<60;j++) 
   a[i][j]=2;  
srand((unsigned)time(NULL));//随机函数作种 
for(i=1;i<14;i++)//for开始  
  for(j=1;j<60;j++) 
  { 
   n=rand()%22;//随机函数 
   if(n<17) a[i][j]=’ ’; 
  }//for结束 
a[1][0]=’ ’;//给迷宫留入口 
a[1][1]=’ ’; 
a[1][2]=’ ’; 
a[1][3]=’ ’; 
a[13][56]=’ ’;//给迷宫留出口 
a[13][57]=’ ’; 
a[13][58]=’ ’; 
a[13][59]=’ ’; 
}  
/*栈初始化*/ 
void InitStack(STACK *S) 
{ 
S->top=NULL; 
S->length=NULL; 
} 
/*元素e入栈*/ 
int Push(STACK *S,int e) 
{ 
SNode *p; 
p=(SNode *)malloc(sizeof(SNode)); 
if(!p) return ERROR; 
p->data=e; 
p->next=S->top; 
S->top=p; 
S->length++; 
return OK; 
} 
/*栈顶元素出栈,e带回栈顶元数*/ 
int Pop(STACK *S,int *e) 
{ 
SNode *p; 
if(S->top==NULL) return ERROR; 
p=S->top; 
*e=p->data; 
S->top=p->next; 
S->length--; 
delete p; 
return OK; 
} 
/*判断S是否为空栈*/ 
int Empty(STACK S) 
{ 
    if(S.top==NULL) return OK; 
    return ERROR; 
} 
int main() 
{ 
    int i,j,path,speed=0; 
    long timei,timej; 
    char m=12; 
/*   for(int i=0;i<100;i++) 
    { 
            m=i; 
            cout<<i<<"   "<<m<<endl; 
    } 
    system("pause");*/ 
    STACK S;                 //定义一个用于存储老鼠走过的路线的栈 
    InitMaze();              //随机成生迷宫 
    InitStack(&S);           //初始化栈 
    i=1; 
    j=0; 
    a[i][j]=m;             //初始化老鼠位置 
    ShowMaze();              //显示迷宫 
    cout<<"\n\t\t\t请选择速度:1 快速 2  慢 "<<endl; 
    while(speed!=1 && speed!=2) cin>>speed; 
    while(i>=0 && i<15 && j>=0 && j<60)//开始钻迷宫 
    { 
     ShowMaze();              //显示迷宫 
     if(speed==2)             //选择2较慢时进入空循环延时 
     for(timei=0;timei<TIMEMAX;timei++) 
     for(timej=0;timej<TIMEMAX;timej++);//空循环,延时用的! 
     if(i==13 && j==59)       //判断是否到达出口 
  { 
   cout<<"\n\t\t\t\t成功走出!所用的步数为:"<<S.length<<endl; 
   system("pause"); 
   exit(1); 
  } 
  if(a[i][j+1]==’ ’)             //向右走一步 
  { 
   char d=26; 
   a[i][j]=d; 
   j=j+1; 
   a[i][j]=m; 
   Push(&S,RIGHT); 
  } 
  else 
  { 
   if(a[i+1][j]==’ ’)            //向下走一步 
   { 
    char d=25;                
    a[i][j]=d; 
    i=i+1; 
    a[i][j]=m; 
    Push(&S,DOWN); 
   } 
   else 
   { 
    if(a[i-1][j]==’ ’)           //向上走一步 
    { 
     char d=24;                
     a[i][j]=d; 
     i=i-1; 
     a[i][j]=m; 
     Push(&S,UP); 
    } 
    else 
    { 
     if(a[i][j-1]==’ ’)          //向左走一步 
     { 
     char d=27; 
      a[i][j]=d; 
      j=j-1; 
      a[i][j]=m; 
      Push(&S,LEFT); 
     } 
     else                        //遇到障碍往回走一步 
     { 
      if(Empty(S)==OK)           //判断是否回到起点了,是则退出程序 
      { 
       cout<<"\n\t\t\t\t@^@  迷宫没有出路!  @^@\n"<<endl; 
       system("pause");  
       exit(1); 
      } 
      else 
      { 
       if(Pop(&S,&path)==OK)         //判断能否取回上一步路径 
       { 
        switch(path) 
        { 
         case LEFT: 
          a[i][j]=’=’; 
          j=j+1; 
          a[i][j]=m; 
          break; 
         case UP: 
          a[i][j]=’=’; 
          i=i+1; 
          a[i][j]=m; 
          break; 
         case DOWN: 
          a[i][j]=’=’; 
          i=i-1; 
          a[i][j]=m; 
          break; 
         case RIGHT: 
          a[i][j]=’=’; 
          j=j-1; 
          a[i][j]=m; 
          break; 
        }                                           //结束分支语句switch 
       }                                            //结束判断能否取回上一步路径 
      } 
     } 
    } 
   } 
  } 
}//结束while循环 
system("pause"); 
return 0; 
}