迷宫求解（包含随机迷宫、求解动画演示）——C语言 数据结构

该程序是一项 “迷宫求解” 类问题，主要功能包含：

①25 X 25迷宫的随机生成

②迷宫求解的动画演示（DFS）

完整代码附最后 : )

功能演示：

界面展示：

迷宫展示：

结果展示：

首先是随机迷宫部分：

大概思路就是先初始化一个矩阵，外圈为“通路”，内层为“墙体”。

1.定义vector容器，用于存放墙体坐标，先将起点装入容器

2.在容器中随机选取一个墙体，满足“四周无通路或只有一个通路”条件时，将墙体拆除（改为通路）并从容器中移除，随后将该墙体四周的墙体装入容器

流程图演示：

在此使用较小矩阵用于演示

代码部分：

void create_mg()//随机生成迷宫{//初始化迷宫：内部为墙体；外围为通路，当做屏障for(int i=0; i<Y; i++){mg[0][i]=0;mg[X-1][i]=0;}for(int i=1; i<X-1; i++)for(int j=0; j<Y; j++){if(j==0||j==Y-1)mg[i][j]=0;elsemg[i][j]=1;}//分别对应着上下左右方向int dRow[] = {1, 0, -1, 0};int dCol[] = {0, -1, 0, 1};//用于存储墙体坐标vector QX,QY;QX.push_back(start_x);//从起点开始QY.push_back(start_y);while(QX.size())//拆墙{//根据当前时间，生成一个随机数种子srand((unsigned int)(time(NULL)));int index=rand()%(QX.size());//随机生成一个坐标，选取一堵墙int x=QX[index];int y=QY[index];int flag=0;//记录该墙四周通路个数int r,c;for(int i=0; i<4; i++){r=x+dRow[i];c=y+dCol[i];if(mg[r][c]==0)flag++;}if(flag<=1)//当该墙体四周通路有一条或没有时，则该墙改为道路{mg[x][y]=0;for(int i=0; i<4; i++){r=x+dRow[i];c=y+dCol[i];if(mg[r][c]==1)//将该墙四周的墙加入队列{QX.push_back(r);QY.push_back(c);}}}//将当前墙移除队列QX.erase(QX.begin()+index);QY.erase(QY.begin()+index);}}

其次是迷宫求解部分：

为了方便理解，我设计了box结构体，用于表示路径的坐标与方向

struct box{int x,y;//坐标int dir;//方向：右1 下2 左3 上4};

迷宫求解问题，路径部分当然要用栈来存放啦，方便回溯

思路很简单：

按照“右下左上”顺时针方向进行摸索，能走通的就走，死路就回溯，即将该点路径出栈，并将已走过的路线做上标记。回溯到起点即代表迷宫无解，到终点就是求解完成。

但为了完成动画效果还是需要下亿点功夫：

①每走一步需重新打印一次迷宫，这就少不了清屏功能，使用system(“cls”)虽然方便，但会出现较为严重的闪屏现象，做过动画演示程序的应该体验过，虽然不影响功能，但视觉体验很糟糕。我也是通过网上学习两个函数来代替system(“cls”)，解决闪屏。

void gotoxy(int x,int y)//将光标移动到（x,y）位置{HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);//获取标准输出设备句柄COORD pos= {x,y}; //坐标位置SetConsoleCursorPosition(handle,pos); //设置控制台光标位置}void HideCursor()//隐藏光标{CONSOLE_CURSOR_INFO cursor_info= {1,0}; //0表示隐藏光标SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE),&cursor_info);}

②为了有更好的视觉体验，我用了不同颜色区分墙体，路线与已走路线。即打印路线前调用变色函数，打印后恢复原色

HANDLE hout = GetStdHandle(STD_OUTPUT_HANDLE);//颜色void cout_green()//绿色{SetConsoleTextAttribute(hout, 2);}void cout_red()//红色{SetConsoleTextAttribute(hout, 4);}void recover()//白色{SetConsoleTextAttribute(hout, 1|2|4);}

代码部分：

void play_mg(){//分别对应着上下左右方向int dRow[] = {0, 1, 0, -1};int dCol[] = {1, 0, -1, 0};box start;//起始位置start.x=start_x;start.y=start_y;path.push(start);while(!path.empty()){box temp;bool flag=false;//判断该坐标是否有通路int x = path.top().x;int y = path.top().y;mg[x][y]=1;//该坐标已经过,设置为墙for(int i=0; i<4; i++) //向四个位置进行试探,方向：右1 下2 左3 上4{int r=x+dRow[i];int c=y+dCol[i];if(mg[r][c]==0){temp.x=r;temp.y=c;temp.dir=i+1;path.push(temp);flag=true;break;}}if(x==X-3&&y==Y-3)//到达终点break;mglx[x][y]=temp.dir+1;//该坐标已经过,右2 下3 左4 上5if(!flag)//若该坐标点无通路，则回溯{box t=path.top();mglx[t.x][t.y]=6;//回溯后要把该坐标设为不可走路线path.pop();}HideCursor();gotoxy(0,0);Sleep(speed);//设置速度show_mg();}}

其余部分代码就是一些简单的界面设计与细节处理，很好理解

完整代码附上：

#include#include//栈 #include//容器 #include//获取当前时间 #include //颜色改变，时停 #include//清屏 using namespace std;#define X 27//迷宫大小 #define Y 27#define start_x 2//起点#define start_y 2#define speed 30//速度 struct box{int x,y;//坐标int dir;//方向：右1 下2 左3 上4};int mg[X][Y];//初始迷宫int mglx[X][Y];//展示迷宫路线，因原迷宫会被打乱stack path;//路线，包含坐标与方向信息HANDLE hout = GetStdHandle(STD_OUTPUT_HANDLE);//颜色void create_mg();//随机生成迷宫void copy_mg();//复制迷宫void play_mg();//完成迷宫路线求解void show_path();//坐标路线展示 void show_mg();//迷宫路线展示void cout_green();//打印绿色void cout_red();//打印红色void recover();//恢复白色//清屏函数，代替system("cls")，防止闪烁，网上学习void gotoxy(int x,int y);//将光标移动到（x,y）位置void HideCursor();//隐藏光标int main(){while(true){system("cls");char choice;cout<<endl<<endl<<"*****\t欢迎来到迷宫求解问题\t*******"<<endl<<endl<<endl;cout<<"\t[1] 随机生成迷宫."<<endl;cout<<"\t[2] 退出游戏."<<endl<<endl;cout<<"\t\t随机生成 "<<X-2<<" X "<<Y-2<<" 的迷宫"<<endl;cout<<"\t\t\t\t——QLU"<<endl;cout<<"****************************************"<<endl<<endl;cout<>choice;if(choice=='1'){system("cls");while(true){create_mg();if(mg[X-3][Y-3]==0)//若终点是一堵墙，则重新生成迷宫break;}copy_mg();show_mg();system("pause");play_mg();show_path();}else if(choice=='2')return 0;elsecout<<"请输入正确的选择!"<<endl;system("pause");}}void create_mg()//随机生成迷宫{//初始化迷宫：内部为墙体；外围为通路，当做屏障for(int i=0; i<Y; i++){mg[0][i]=0;mg[X-1][i]=0;}for(int i=1; i<X-1; i++)for(int j=0; j<Y; j++){if(j==0||j==Y-1)mg[i][j]=0;elsemg[i][j]=1;}//分别对应着上下左右方向int dRow[] = {1, 0, -1, 0};int dCol[] = {0, -1, 0, 1};//用于存储墙体坐标vector QX,QY;QX.push_back(start_x);//从起点开始QY.push_back(start_y);while(QX.size())//拆墙{//根据当前时间，生成一个随机数种子srand((unsigned int)(time(NULL)));int index=rand()%(QX.size());//随机生成一个坐标，选取一堵墙int x=QX[index];int y=QY[index];int flag=0;//记录该墙四周通路个数int r,c;for(int i=0; i<4; i++){r=x+dRow[i];c=y+dCol[i];if(mg[r][c]==0)flag++;}if(flag<=1)//当该墙体四周通路有一条或没有时，则该墙改为道路{mg[x][y]=0;for(int i=0; i<4; i++){r=x+dRow[i];c=y+dCol[i];if(mg[r][c]==1)//将该墙四周的墙加入队列{QX.push_back(r);QY.push_back(c);}}}//将当前墙移除队列QX.erase(QX.begin()+index);QY.erase(QY.begin()+index);}}void play_mg(){//分别对应着上下左右方向int dRow[] = {0, 1, 0, -1};int dCol[] = {1, 0, -1, 0};box start;//起始位置start.x=start_x;start.y=start_y;path.push(start);while(!path.empty()){box temp;bool flag=false;//判断该坐标是否有通路int x = path.top().x;int y = path.top().y;mg[x][y]=1;//该坐标已经过,设置为墙for(int i=0; i<4; i++) //向四个位置进行试探,方向：右1 下2 左3 上4{int r=x+dRow[i];int c=y+dCol[i];if(mg[r][c]==0){temp.x=r;temp.y=c;temp.dir=i+1;path.push(temp);flag=true;break;}}if(x==X-3&&y==Y-3)//到达终点break;mglx[x][y]=temp.dir+1;//该坐标已经过,右2 下3 左4 上5if(!flag)//若该坐标点无通路，则回溯{box t=path.top();mglx[t.x][t.y]=6;//回溯后要把该坐标设为不可走路线path.pop();}HideCursor();gotoxy(0,0);Sleep(speed);//设置速度show_mg();}}void show_path()//展示坐标路线{if(path.empty()){cout<<"此迷宫无解"<<endl;return;}box temp[100];int length=0;while(!path.empty()){temp[length]=path.top();length++;path.pop();}cout<<"方向路线:"<<endl;cout<";for(int i=length-1; i>=0; i--){if(temp[i].dir==1)cout<";else if(temp[i].dir==2)cout<";else if(temp[i].dir==3)cout<";else if(temp[i].dir==4)cout<";}cout<<"终点"<<endl<<endl;cout<<"坐标路线："<<endl;cout<";for(int i=length-1; i>=0; i--){cout<<"("<<temp[i].x-1<<","<<temp[i].y-1<";}cout<<"终点"<<endl;}void show_mg()//展示迷宫路线{for(int i=0; i<X; i++){for(int j=0; j<Y; j++){//墙■路右2→ 下3↓ 左4← 上5↑ 错×if(i==start_x&&j==start_y)cout<<"☆";else if(i==X-3&&j==Y-3)cout<<"★";else if(mglx[i][j]==1)cout<<"■";else if(mglx[i][j]==2){cout_green();cout<<"→";recover();}else if(mglx[i][j]==3){cout_green();cout<<"↓";recover();}else if(mglx[i][j]==4){cout_green();cout<<"←";recover();}else if(mglx[i][j]==5){cout_green();cout<<"↑";recover();}else if(mglx[i][j]==6){cout_red();cout<<"×";recover();}elsecout<<"";}cout<<endl;}}void copy_mg()//复制迷宫{for(int i=0; i<X; i++){for(int j=0; j<Y; j++){mglx[i][j]=mg[i][j];}}}void cout_green()//绿色{SetConsoleTextAttribute(hout, 2);}void cout_red()//红色{SetConsoleTextAttribute(hout, 4);}void recover()//白色{SetConsoleTextAttribute(hout, 1|2|4);}void gotoxy(int x,int y)//将光标移动到（x,y）位置{HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);//获取标准输出设备句柄COORD pos= {x,y}; //坐标位置SetConsoleCursorPosition(handle,pos); //设置控制台光标位置}void HideCursor()//隐藏光标{CONSOLE_CURSOR_INFO cursor_info= {1,0}; //0表示隐藏光标SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE),&cursor_info);}