c++ 迷宫问题(给出迷宫，制动寻径问题)实例源码下载

【实例截图】

【核心代码】

#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>//因为要产生随机函数种子
#include <windows.h>//因为要用Sleep延时函数

#define MAX_X 20  //定义迷宫大小
#define MAX_Y 30

int maze[MAX_X][MAX_Y];

class stack_for_maze//迷宫行走路线存储专用栈类！
{
private:
 struct node//结点用来记录压栈的迷宫坐标
 {
  int x;
  int y;
  char direction; //上一步的行走方向（即如何来到这里的）   
  node* next;
 };
 node* head;
public:
 stack_for_maze()
 {
  head=NULL;
 }
 ~stack_for_maze()
 {
  node* p=head;
  while(head!=NULL)
  {
   head=head->next;
   delete p;
   p=head;
  }
 }
 void push(int xx,int yy,char ddirection)//压栈，将坐标和行走方向压栈
 {
  node* new_node;
  new_node=new node;
  if(new_node!=NULL)
  {
   new_node->x=xx;
   new_node->y=yy;
   new_node->direction=ddirection;
   new_node->next=NULL;
   
   if(head==NULL)
    head=new_node;
   else
   {
    new_node->next=head;
    head=new_node;
   }  
  }
  else
   cout<<"\n因为内存分配失败导致本次压栈失败！！！\n";
 }
 node* pop(int& xx,int& yy)//出栈时带回栈顶元素坐标
 {
  if(head!=NULL)
  {
   node* p=head;
   head=head->next;
   xx=p->x;
   yy=p->y;
   delete p;
  }
  else
  {
   cout<<"\n因为栈已空导致本次出栈失败\n";
  }
  return head;
 }
 void print()//输出栈内元素
 {
  if(head!=NULL)
  {
   node* p=head;
   while(p!=NULL)
   {
    cout<<"  "<<p->x<<"   "<<p->y<<"   "<<p->direction<<endl;
    p=p->next;
   }
  }
  else
   cout<<"\n栈为空，打印失败\n";
 }
};
void CreateMaze()//创建迷宫
{
 int max_way=MAX_X*MAX_Y;//产生通路的参数，值越大障碍越少
 int x,y;

 for(x=0;x<MAX_X;x  )
  for(y=0;y<MAX_Y;y  )
   maze[x][y]=1; //先把迷宫全部设为墙壁

 srand((unsigned)time(NULL));//随机函数种子发生器（以时间做参数）
 for(int i=0;i<=max_way;i  )//随机构建迷宫通路
 {  
  x=rand()%(MAX_X-2) 1;
  y=rand()%(MAX_Y-2) 1;
  maze[x][y]=0;
 }
 
 maze[1][1]=0;//入口
 maze[MAX_X-2][MAX_Y-2]=0;//出口

 maze[0][1]=3;
 maze[MAX_X-1][MAX_Y-2]=0;
}
void PrintMaze()//输出迷宫的当前状态
{
 int x,y;
 system("cls");//清屏
 cout<<endl;
 for(x=0;x<MAX_X;x  )
 {
  for(y=0;y<MAX_Y;y  )
  {
   if(maze[x][y]==0){cout<<"  ";continue;}//通路
   if(maze[x][y]==1){cout<<"■";continue;}//墙
   if(maze[x][y]==2){cout<<"×";continue;}//死胡同
   if(maze[x][y]==3){cout<<"↓";continue;}//向下走
   if(maze[x][y]==4){cout<<"→";continue;}
   if(maze[x][y]==5){cout<<"←";continue;}
   if(maze[x][y]==6){cout<<"↑";continue;}
   if(maze[x][y]==7){cout<<"※";continue;}//当前站立位置
   }
  cout<<endl;
 }
 Sleep(2);//延时函数
}
void move(stack_for_maze &s)
{
 int x=1,y=1;//出发点
 while(1)
 {
  maze[x][y]=2;

  //-----------------------向下
  if(maze[x 1][y]==0)
  {
   s.push(x,y,'D');
   maze[x][y]=3;//将当前位置做一个向下的标记↓用代码3表示
   x=x 1;//向下走到一个新位置
   maze[x][y]=7;//标记当前站立位置为7，用符号※表示
   PrintMaze();
   if((x==MAX_X-1)&&(y==MAX_Y-2))
   {
    s.push(x,y,'*');
    cout<<"\n成功走出！！！\n";
    return;
   }
   else
    continue;
  }

  //-----------------------向右
  if(maze[x][y 1]==0)
  {
   s.push(x,y,'R');
   maze[x][y]=4;//将当前位置做一个向右的标记→用代码4表示
   y=y 1;//向右走到一个新位置
   maze[x][y]=7;//标记当前站立位置为7，用符号※表示
   PrintMaze();
   if((x==MAX_X-1)&&(y==MAX_Y-2))
   {
    s.push(x,y,'*');
    cout<<"\n成功走出！！！\n";
    return;
   }
   else
    continue;
  }

  //-----------------------向上
  if(maze[x-1][y]==0)
  {
   s.push(x,y,'U');//当前位置压栈
   maze[x][y]=6;//将当前位置做一个向上的标记↑用代码6表示
   x=x-1;//向上走到一个新位置
   maze[x][y]=7;//标记当前站立位置为7，用符号※表示
   PrintMaze();
   if((x==MAX_X-1)&&(y==MAX_Y-2))
   {
    s.push(x,y,'*');
    cout<<"\n成功走出！！！\n";
    return;
   }
   else
    continue;
  }

  //-----------------------向左
  if(maze[x][y-1]==0)
  {
   s.push(x,y,'L');
   maze[x][y]=5;//将当前位置做一个向左的标记←用代码5表示
   y=y-1;//向左走到一个新位置
   maze[x][y]=7;//标记当前站立位置为7，用符号※表示
   PrintMaze();
   if((x==MAX_X-1)&&(y==MAX_Y-2))
   {
    s.push(x,y,'*');
    cout<<"\n成功走出！！！\n";
    return;
   }
   else
    continue;
  }

  //--------------------上下左右均不通则回退，即出栈一次，如果出栈导致栈空则说明无路可走了！
  if(s.pop(x,y)==NULL&&maze[x-1][y]!=0&&maze[x][y-1]!=0&&maze[x][y 1]!=0&&maze[x 1][y]!=0)
  {
   cout<<"\n没有找到合适路径！！！\n";
   maze[0][1]=7;//没有找到路，就站在起点吧！
   if(maze[1][1]!=1)maze[1][1]=2;
   return;
  }
 }
}
void main()
{
 CreateMaze();//创建迷宫
 PrintMaze();//输出当前迷宫的初始状态
 stack_for_maze stack;//定义一个栈的对象，用来记录行走路线
 move(stack);//行走中……
 PrintMaze();//输出迷宫的最终状态
 getchar();
 getchar();
}