迷宫问题—数据结构实践作业
✅作者简介：大家好,我是新小白2022，让我们一起学习，共同进步吧🏆
📃个人主页：新小白2022的CSDN博客
🔥系列专栏：算法与数据结构
💖如果觉得博主的文章还不错的话，请点赞👍+收藏⭐️+留言📝支持一下博主哦🤞
一、 问题描述及分析🏮
迷宫问题
传说在远古时候，米诺斯国王统治着爱琴海南端的克里特岛。他建造了一座有无数宫室的迷宫，在迷宫中喂养了一头人身牛头的恶兽——米诺牛。为了供奉它，米诺斯要希腊的雅典每九年进贡七对童男女喂米诺牛。当时，雅典有位名叫忒休斯的王子，他不忍人民遭受这种灾难，毅然决定跟随第四批被进贡的童男女去克里特杀死米诺牛。在克里特，英勇的忒休斯赢得了米诺斯的女儿的爱慕。她交给忒休斯一个线团，让他按下面规则边走边放线：
（1）每到一个岔口，找没有铺上线的路走；若找不到未铺上线的路，就沿原来的路返回到前一个岔口。
（2）不走已铺上两条线的路。
用这种方法，忒休斯终于杀死米诺牛，胜利的走出迷宫。
二、 功能模块及数据结构描述✅
数据结构描述🐱🏍
（1）使用深度优先创建地图
首先确定一个起始点(ROAD)， 接着判断 下一步挖墙的方向(四个方向都要判断)；然后找到方向，就开始挖墙(开路ROAD)；随机选定方向后(用当前位置坐标)，循环遍历9个宫格之后再 判断是否可以挖墙；以map[posx][posy]当前位置为起始，遍历周围9个位置
（2）由基础图来显示迷宫样貌
通过动态分配内存后的，二维数组MAP所存入的数据进行显示ROAD与WALL，这样显示在大家眼前就比较清晰明朗
（3）创建基础地图
首先进行动态为二维数组分配内存空间，接着进行初始化；然后为特殊情况进行赋值操作，防止墙壁被挖穿
（4）更改光标的位置函数
善用DOS命令，和库函数进行编写光标移动函数
（5）设置外围(其他)Road位置
为50*50的迷宫外围设置初始值
（6）指定位置删除墙
只用输入坐标位置，就可以进行指定位置删除墙壁
（7）指定位置添加墙
只用输入坐标位置，就可以进行指定位置添加墙壁
功能模块✨
图一 操作介绍
迷宫显示样貌
图二 迷宫展示
遍历迷宫过程显示
图三 搜索过程
显示走出迷宫的路径
图四 显示一条路径
三、主要算法流程描述及部分核心算法✉️
流程描述
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ROQ66y3u-1673688331267)(D:\Program Files (x86)]\Typora\user-images\wps5.jpg)
部分核心算法
1、深度优先搜索演示函数
先进行走迷宫(按照已设置好的迷宫路径)，
自行寻找出路，接着进行显示 已找到的路径。
首先遵循右上下左的原则，一次选取一个方向进行搜索出路
边搜索边进行输出显示此时位置，动态显示位置
当搜索演示完毕以后,输出栈中内容,就是迷宫的路径，
输出栈的内容,保存的就是迷宫路径，
2、广度优先搜索演示函数
以当前位置为起点，进行广度优先搜索，用队列进行存储，方便遍历迷宫后进行显示一条通路。
取出当前队列的位置信息,开始向四周遍历；
四个方向同时进行搜索,而且一直搜索,直到搜索到了出口；
每走四个方向,即遍历一次;让last++;第一个数出队列,让队列的第二个数开始向上下左右进行搜索；
当搜索演示完毕以后,输出队列中内容,就是迷宫的路径，
输出队列的内容,保存的就是迷宫路径。
3、递归-随机生成迷宫函数
利用随机生成数，先采用覆盖打乱法进行操作，防止随机出重复数字。首先确定一个起始点(ROAD)接着判断;下一步挖墙的方向(四个方向都要判断) 1、保证不走已走的路——第一行、第一列存储数据(确定方向时)详细步骤第一列、第二列。先进行打乱(挖墙前循环四次)交换覆盖打乱法，后循环遍历4次就可以达到 先判断四个不同方向
然后找到方向，就开始挖墙(开路ROAD)
(1)防止出现环结构 —— prim算法生成最小生成树思想考虑map[posx][posy]，下标所可以操控 挖墙的上下左右之前打乱的(二维数组存储的第一列和第二列数据)现在用他们来为当前位置下标，进行判断向哪个方向挖墙！ 确定后，会出现当前点位置斜着移动的情况 (如x+1&&y-1)这时就要用强制条件，只让横着或竖着移动，也就是 posx或posy只能有一个改变(若不改变也可以)
(2)随机选定方向后(用当前位置坐标)，循环遍历9个宫格之后再 判断是否可以挖墙；以map[posx][posy]当前位置为起始，遍历周围9个位置；如果循环9个位置时，当前位置满足不是ROAD 而且 只用移动一小步；flag不会++操作；
(3)flag++操作目的就是判断该坐标map[posx][posy]是否可以挖成路；只有 flag<=1时，才会有挖开当前位置(ROAD)的操作；简单地说就是，以当前map[posx][posy]为起始点的9个小格子；只需移动一下，而且移动之后位置是WALL；才可以判断可以挖开当前位置map[posx][posy](置为ROAD)
四、系统使用说明🎉
输入a：深度优先算法显示寻找出路的路径
输入b: 广度优先算法显示寻找出路的路径
输入d: 去除当前显示的所有路径
输入e: 重新生成迷宫，采用随机生成使用c的思想
输入f: 指定位置添加墙壁
输入g: 指定位置删除墙壁
输入h: 退出迷宫游戏并显示项目成员信息
五、问题及解决办法😋
问题一：迷宫只有一条正确的道路，怎样实现？
那么基于唯一道路的原则，我们向某个方向挖一块新的区域时，要先判断新区域是否有挖穿的可能，如果可能挖穿要立即停止并换个方向再挖。挖之前要确保上下左右四个位置中只有一个位置是路。
我们可以把一个N*N的迷宫建立的过程想象成挖地道。我们定义初始状态时，迷宫的每个格子都为墙壁（WALL），墙壁挖掉后就变成道路（ROUTE）我们需要把墙壁一块块挖掉才能挖出迷宫中的一条条通道。
问题二：怎样防止防止无限挖迷宫？
设置边界一个很简单的办法就是让迷宫的最外面一圈的格子都为ROUTE，这么一来不管怎么挖，都不会挖穿了
问题三：怎样才可不走已走过的路？
那么我们就让每次挖的时候四个方向都尝试一遍，用到随机生成数和覆盖防止重复法！保证四个方向都能遍历到，类似于随机输出在0-9之间的10个数字，而且要保证这10个数字不重复。
问题四：致命的缺陷就是出现了环，怎样避免？
环是什么，简单来说就是我站在迷宫中朝着一个方向走，在不走回头路的情况下能够走回到起点，这就是环。判断上下左右，是否为ROAD,若有ROAD就说明，右形成环的风险！
问题五：删除墙壁写入后，造成显示界面不清晰怎么处理？
先进行清屏操作，接着显示页面的欢迎界面，显示图像界面和显示菜单界面
问题六：在清除所显示的页面操作后，仍会重复显示上次已有的内容？
调用改变窗口大小的函数出现了问题，这里就需要增加相关参数
问题七：出现显示地图和功能选项混合显示，怎样处理？
首先修改操作光标的函数，接着进行更改预设的宏定义MAXSIZE数值，然后显示菜单，接着进行更改窗口大小参数的设置
六、 课程设计总结🦄
这一次的实践中与用到了遍历的有关知识，结合到栈和队列的知识，在遍历方面上，分别利用到了栈的提供后进先出的特点和队列先进先出的特点，将两种方式相结合，避开两种方式各自的缺点，来将程序更加完善简洁，在解决问题的过程中，我们发现有不同类型的问题，我们选择逐个解决，然后进行各个部分的融合，使我们对迷宫游戏的原理有了更深的了解，距离真正的迷宫还有很大的差距，仍需我们在课下继续学习更多的知识。
——小郭
在这次解决迷宫问题的过程中学习了很多知识，深刻了解并实际应用了深度优先遍历和栈。DFS更适合模拟机器人走迷宫的方式，看到一个方向是通的，就一直走下去，遇到死胡同就退回。在实际应用过程中，当到达某点（i，j）后将对应点置“×”，其他未到达过的点其值只能是“囧”或“▲”，可与未到达过的点区分开来，且占用内存少。在本次解决实际问题的过程中，感受到了团队合作的重要性，一起发现且讨论解决问题，在团队合作中让我成长了很多。
——小吴
在迷宫求解的问题中，有两种解法，可以采用深度优先遍历和广度优先遍历。深度优先遍历可以借助栈实现，广度优先遍历可以借助队列实现。具体来说，首先将入口坐标入队，在队列不为空时循环以下操作:出队一次，如当前出队的坐标为出口坐标，则结束循环并输出路径，否则找出相邻的可走的路径的坐标，并将这些坐标入队，将这些坐标标记，避免重复搜索；若队列为空，仍找不到出口，那么就是不存在路径。在这个问题的解决过程中，可以加深对广度优先遍历的理解程度。
——小潘
迷宫小游戏的构思，采用深度优先搜索进行创建随机迷宫，接着进行DFS和BFS的遍历迷宫寻找迷宫出路的操作；这里历经3天的纠结和调整，在老师和同学的协助下终于克服困难，走近迷宫的一小步；接着就思考怎样进行防止形成环结构和走重复的路，然后慢慢的调试、更改和不断完善；进行指定位置墙壁的增添和界面的优化操作！感谢团队的齐心协力和老师的指导，才得以将该小游戏做的活灵活现。
——小张
七、源代码🗝
#include <stdio.h>
#include <iostream>
#include <conio.h>
#include <Windows.h>
#include <time.h>
#include <math.h>
#define WALL 0
#define ROAD 1
#define MAXSIZE 50
#define ARRIVEROAD 2
using namespace std;//用于记录位置信息
struct PosiationInformation
{int x, y;
};struct Queue
{int x, y;int next;
};
//更改光标函数
HANDLE hout = GetStdHandle(STD_OUTPUT_HANDLE);//这些代表着上下左右,当然我们在调用前会随机打乱
int randDirection[4][2] = {{ 1, 0 }, { -1, 0}, { 0, 1 }, { 0, -1}
};
int temp;
int randNumber;
int posx, posy;//使用深度优先创建地图
void createMap(int **map, int x, int y) {//随机获取当前节点就进行设置为ROAD,第一次为入口（自定义的）map[x][y] = ROAD;//我们将根据当前位置随机获取一个要挖的墙,//不可以是像上下左右这样的固定的for (int i = 0; i < 4; ++i) {randNumber = rand() % 4;//第一列数据-//生成不重复随机数(交换覆盖代码)——让数组中数据不重复出现//保证在该范围内(可随机数据范围),数组中的数据不同temp = randDirection[0][0];randDirection[0][0] = randDirection[randNumber][0];randDirection[randNumber][0] = temp;//第二列数据-//生成不重复随机数(交换覆盖代码)——让数组中数据不重复出现temp = randDirection[0][1];randDirection[0][1] = randDirection[randNumber][1];randDirection[randNumber][1] = temp;}//开始挖墙,向四周随机挖,四个方向总是会出现,//但是每次出现的顺序不同;for (int i = 0; i < 4; ++i) {
//变量r的作用?—— r判断是否执行递归int r = 0;//首先获取当前位置posx = x;posy = y;//当然我们这里默认 挖墙距离为1,即某个方向只能挖一次,//就要切换下个方向挖,这样迷宫会更加复杂//在randDirection[4]里面 获取接下来要向哪开始挖posx = posx + randDirection[i][0];posy = posy + randDirection[i][1];//排除回路,如果当前方向是路,那就没必要继续,//那就意味着这里已经走过了,如果此时还按照程序走下去是会出现死归的;//所以我们这个方向已经行不通了,需要换一个方向;if (map[posx][posy] == ROAD) {r++;//}//先判断当前路径前面的墙能不能挖;(如何做到判断？)/*第一层for有 posx - 1, posx, posx + 1第二层for有 posy - 1, posy, posy + 1那么3 * 3 = 9,这么下来共有九种情况,而这也恰恰对应了,当前路径前面那个墙周围九格的坐标位置若if(abs(j - posx) + abs(k - posy) == 1)成立,(j==posx或k==posy)则证明 行 与 列 其中必有一个为posx或posy而这又对应当前路径 前面那面墙 上下左右 四种情况;若map[j][k] == ROAD成立,则证明该已经是路径(当前路径前面的墙的 上下左右 某一个方向已经是路径);那就没必要挖墙了;因为这会造成地图挖穿,或者形成回路;或者二叉树分支相互通(将地图看成二叉树)*/
//j==posx 或 k==posy,这确定 该位置(坐标)位于 现位置的上下左右(或现位置)
//变量flag的作用？？—— 记录是否可以对该墙操作(标志变量)//flag一旦进行++ 说明不可 在当前操作墙位置进行挖掘//现位置可以让flag进行一次++操作;//遍历9个位置flag的值会 大于等于1int flag = 0; for (int j = posx - 1; j < posx + 2; j++) {for (int k = posy - 1; k < posy + 2; k++) {if (abs(j - posx) + abs(k - posy) == 1 && map[j][k] == ROAD) {flag ++;}}}//这里我们让flag > 1,因为肯定有一次满足if条件的,就是当前位置;//我们用 r判断是否执行递归;//如果r == 0,证明 flag < 1以及没有出现回路,此时指向else将该墙挖掉,并按照目前方向继续下去(进行递归)//如果r != 0,证明当前的随机方向出现了以上情况,那就证明该方向已经行不通了,那就让for循环继续,下一个方向;//此时不能进行递归,否则会出现死归;if (flag > 1) {//跳过本次方向(当前位置——即将操作的墙位置)r ++;} else {//否则就可以挖墙map[posx][posy] = ROAD;}
//当前位置可以挖掘后，继续以 现坐标进行迭代(递归)！//以现坐标为起点，再进行判断下一步的挖墙位置(可同时进行)if (r == 0) {//以此为节点递归,递归结束条件就是当所有方向不成立的时候,就会来时回溯;createMap(map, posx, posy);}}
}
void listMap(int **map) {for (int i = 0; i < MAXSIZE; ++i) {for (int j = 0; j < MAXSIZE; ++j) {printf("%d ", map[i][j]);}printf("\n");}
}
//由基础图来显示迷宫样貌
void printfMap(int **map) {for (int i = 0; i < MAXSIZE; i++) {for (int j = 0; j < MAXSIZE; j++) {if (map[i][j] == ROAD) {printf(" ");} else if (map[i][j] == WALL) {printf("囧");}}printf("\n");}
}//创建基础地图
int **getMap() {//创建地图并申请空间int **map = (int **)malloc(MAXSIZE * sizeof(int *));for (int i = 0; i < MAXSIZE; i++) {map[i] = (int *)malloc(MAXSIZE * sizeof(int));}//对地图进行初始化for (int i = 0; i < MAXSIZE; ++i) {for (int j = 0; j < MAXSIZE; ++j) {map[i][j] = WALL;}}//初始化地图将地图的外围设为路径,为了防止地图挖穿for (int i = 0; i < MAXSIZE; ++i) {map[0][i] = ROAD;map[MAXSIZE - 1][i] = ROAD;map[i][0] = ROAD;map[i][MAXSIZE - 1] = ROAD;}return map;
}//更改光标的位置
void SetPosition(int line, int col){ //更改光标的位置static COORD coord;coord.X = col * 2;coord.Y = line;SetConsoleCursorPosition(hout, coord);
}
//这个代码网上学的//改变控制台窗口大小
void ChangeConsoleSize(int line, int col) { //改变控制台窗口大小char LINE[10], COL[10], FINAL[50] = { '\0' };sprintf(LINE, "%d", line);//sprintf函数把结果输出到指定的字符串中sprintf(COL, "%d", col * 2);strcpy(FINAL, "mode con cols=");strcat(FINAL, COL);strcat(FINAL, " lines=");strcat(FINAL, LINE);system(FINAL);//函数最后的结果就相当于cmd命令：mode con lines=123 cols=123<enter>
}
//设置外围(其他)Road位置
void setIn_OutMap(int **map) {map[2][1] = ROAD;for (int i = MAXSIZE - 3; i >= 0; i--) {if (map[i][MAXSIZE - 3] == ROAD) {map[i][MAXSIZE - 2] = ROAD;break;}}
}
void Welcome() {SetConsoleTextAttribute(hout, 11);SetPosition(2, 16);cout << "出版商:小张";SetPosition(4, 16);cout << "侵权必究";SetPosition(10, 20);cout << " 欢迎来您到迷宫游戏2.2.1 " << endl;SetPosition(14, 10);cout << "玩命加载中 : ";for (int i = 0; i < 80; ++i) {Sleep(30);printf("+");}system("cls");SetPosition(10, 20);cout << " ~~~~祝您游戏愉快~~~~ ";Sleep(1000);system("cls");
}
//这个代码网上学的
void PrintMenu() {SetConsoleTextAttribute(hout, 11);SetPosition(4, MAXSIZE + 3);cout << "■■■■■■■■操作介绍■■■■■■■■";//cout << "■■■操作介绍■■■";SetPosition(6, MAXSIZE + 3);cout << " 按 a 进行深度优先搜演示";SetPosition(8, MAXSIZE + 3);cout << " 按 b 进行广度优先搜演示";SetPosition(10, MAXSIZE + 3);cout << " 按 c 进行递归搜索演示";SetPosition(12, MAXSIZE + 3);cout << " 按 d 去除所有路径";SetPosition(14, MAXSIZE + 3);cout << " 按 e 重新生成迷宫";SetPosition(16, MAXSIZE + 3);cout << " 按 f 指定位置添加墙" ;SetPosition(18, MAXSIZE + 3);cout << " 按 g 指定位置删除墙" ;SetPosition(20, MAXSIZE + 3);cout << " 按 h 退出迷宫游戏";SetPosition(22, MAXSIZE + 3);cout << "迷宫游戏正在优化中,请大家多多支持！";//cout << "手动搜索路径正在维护中,更多详细信息请关注";SetPosition(23, MAXSIZE + 3);
// SetConsoleTextAttribute(hout, 4);
// cout << " <<My发际线>> ";SetConsoleTextAttribute(hout, 11);SetPosition(24, MAXSIZE + 3);//cout << "■■■游戏介绍■■■";cout << "■■■■■■■■游戏介绍■■■■■■■■";SetPosition(26, MAXSIZE + 3);cout << " 走出迷宫打怪游戏有大佬赞助,团队苦肝";SetPosition(28, MAXSIZE + 3);cout << " 小张的开发,于2022.11.16正式验收";SetPosition(30, MAXSIZE + 3);cout << " 游戏演示了经典迷宫问题,使用prim---";SetPosition(32, MAXSIZE + 3);cout << " 最小生成树算法,随机自动生成迷宫,";SetPosition(34, MAXSIZE + 3);cout << " 使用了三种遍历方式 :";SetPosition(36, MAXSIZE + 3);cout << " 1.递归遍历-RC";SetPosition(38, MAXSIZE + 3);cout << " 2.深度优先-DFS";SetPosition(40, MAXSIZE + 3);cout << " 3.广度优先-BFS";SetPosition(42, MAXSIZE + 3);cout << "X -- 表示死路";SetPosition(44, MAXSIZE + 3);cout << "▽-- 小球走过的路径";SetPosition(46, MAXSIZE + 3);cout << "◆-- 迷宫的正确路径";SetConsoleTextAttribute(hout, 14);
}//递归搜索
bool recursionSearch(int **map, int i, int j) {//system("pause");if (map[MAXSIZE - 3][MAXSIZE - 3] == 2){return true;//如果迷宫出口已被标记为2；证明小球走过了，那么找到出口,然后返回true//使所有的递归方法(由于多次调用recursionSearch函数,在栈中有好多recursionSearch函数,每个都相互独立)//的四个if中的某一个条件成立,进入if执行if中的return;依次下去,直到程序结束;} else {if (map[i][j] == 1) { //如果数组元素为0,则证明可以走;那么就开始按照走路策略开始走(上下左右)map[i][j] = 2;//假设,我们当前的路是通的,为什么要这样,因为我们需要将我们走过的路//标记为2；如果该路走不通,那就回溯（又或者小球一步也没有走直接不需要回溯,因为就没有递归//直接将当前标志为3，这种情况就是小球被墙包围）,将其标志为3;if (recursionSearch(map, i - 1, j)) { //上return false;//这里返回为true意思为;如果小球找到了出口,开始进行回溯;从//map[8][8] == 2开始,一直返回true，然后进入if,还是返回true,连锁反应,直到回溯到main方法程序结束//但是经过我的测试,发现如果这里的if里面全改为false,程序依然照常运行,所以我认为这里的//return 只是起到了结束当前方法的作用,一直结束到main方法,程序结束;}else if (recursionSearch(map, i + 1, j)) { //下return false;}else if (recursionSearch(map, i, j - 1)) { //左return false;}else if (recursionSearch(map, i, j + 1)) { //右return false;} else { //如果四个if都不满足,意思是上下左右都走不通了,小球走进了死路,开始回溯并将该位置//标志为3；证明在这按照该走路策略,是行不通的map[i][j] = 4;return false;//开始回溯,返回false,让所有的if不成立只到退回到某个if成立的位置//然后继续按照策略(上下左右)继续行走}} else { //如果该路不是0 ，那么就可能为 1 ， 2 ，3 ；证明要么为墙（1）不可以走;//要么为死路(3)走不通;要么为已经走过的路(2);那直接返回false;让四个if不成立进而//直接执行最后一个else,使该位置标志为3;return false;}}
}
void ClearMap(int **map) { //清除所有搜索时留下的标记，只留下墙和路for (int i = 0; i < MAXSIZE; ++i) {for (int j = 0; j < MAXSIZE; ++j) {if (map[i][j] != WALL) {map[i][j] = ROAD;}}}
}//深度优先搜索
void DepthFirstSearch(int **map) {int posx = 2, posy = 2;PosiationInformation Stack[(MAXSIZE - 2) * (MAXSIZE - 2)] = { 0 };//使用栈记录 能够通过的位置信息,最后遍历打印出迷宫通路int head = -1;//用来记录(可通过位置)下标while (head >= -1 && (posx != MAXSIZE - 2 || posy != MAXSIZE - 2 + 1)) { //退出条件是当坐标已经到,最大范围了head++;//当前路径肯定能通过,故将当前路径加入到栈中Stack[head].x = posx;Stack[head].y = posy;Sleep(10);if (map[posx][posy + 1] == ROAD) { //如果右边可以走,那就使劲往右边走SetConsoleTextAttribute(hout, 12);SetPosition(posx, posy);cout << "▽";posy++;map[posx][posy] = ARRIVEROAD;} else { //否则就换个方向if (map[posx + 1][posy] == ROAD) { //如果可以往下走SetConsoleTextAttribute(hout, 12);SetPosition(posx, posy);cout << "▽";posx ++;map[posx][posy] = ARRIVEROAD;//标记已经走过了}else { //否则换方向if (map[posx - 1][posy] == ROAD) {//如果可以往上走SetConsoleTextAttribute(hout, 12);SetPosition(posx, posy);cout << "▽";posx --;map[posx][posy] = ARRIVEROAD;} else { //否则换方向if (map[posx][posy - 1] == ROAD) {//如果可以往左走SetConsoleTextAttribute(hout, 12);SetPosition(posx, posy);cout << "▽";posy --;map[posx][posy] = ARRIVEROAD;} else { //否则上下左右都不行,那就让栈的当前节点后退两个,从后退完后的前一个开始,在指向上下左右head -= 2;//当前下标位置不可以走,且 上下左右也不可以SetPosition(posx, posy);SetConsoleTextAttribute(hout, 10);cout << "X";Sleep(10);posx = Stack[head + 1].x;posy = Stack[head + 1].y;}}}}}//当搜索演示完毕以后,输出栈中内容,就是迷宫的路径ClearMap(map);printfMap(map);PrintMenu();//输出栈的内容,保存的就是迷宫路径while (head >= 0) {SetPosition(Stack[head].x, Stack[head].y);SetConsoleTextAttribute(hout, 4);Sleep(10);cout << "◆";SetConsoleTextAttribute(hout, 14);head--;}
}//广度优先搜索
void WidthFirstSearch(int **map) {Queue q[MAXSIZE * MAXSIZE] = {0};int Last = 0;int head = 0;int next = 0;int posx, posy;//对队列初始队列进行初始化q[head].next = -1;q[head].x = 2;q[head].y = 2;while (true) {//取出当前队列的位置信息,开始向四周遍历posx = q[Last].x;posy = q[Last].y;next = q[Last].next;//四个方向同时进行搜索,而且一直搜索,直到搜索到了出口;if (map[posx - 1][posy] == ROAD) { //如果是路,就可以走; map[posx - 1][posy] = ARRIVEROAD;//标记这个方向,证明已经走过了：SetConsoleTextAttribute(hout, 12);SetPosition(posx - 1, posy);cout << "▽";//让当前位置的这个方向入队列,并让头指针++;head++;//当前位置信息入队列;q[head].x = posx - 1;q[head].y = posy;//让Queue指向下一个; 第一次指向 -1q[head].next = Last;//记录Last的值,类似于链表,可以获取上一个值(队列中的下一个)//这是while的终止条件,如果当已经遍历到了出口就break;if ((q[head].x == MAXSIZE - 3) && (q[head].y == MAXSIZE - 2)) {break;}}if (map[posx + 1][posy] == ROAD) {map[posx + 1][posy] = ARRIVEROAD;//标记这个方向,证明已经走过了：SetConsoleTextAttribute(hout, 12);SetPosition(posx + 1, posy);cout << "▽";head++;q[head].x = posx + 1;q[head].y = posy;q[head].next = Last;//指向下一个;第一个指向 - 1if ((q[head].x == MAXSIZE - 3) && (q[head].y == MAXSIZE - 2)) {break;}}if (map[posx][posy - 1] == ROAD) {map[posx][posy - 1] = ARRIVEROAD;//标记这个方向,证明已经走过了：SetConsoleTextAttribute(hout, 12);SetPosition(posx, posy - 1);cout << "▽";head++;q[head].x = posx;q[head].y = posy - 1;q[head].next = Last;if ((q[head].x == MAXSIZE - 3) && (q[head].y == MAXSIZE - 2)) {break;}}if (map[posx][posy + 1] == ROAD) {map[posx][posy + 1] = ARRIVEROAD;//标记这个方向,证明已经走过了：SetConsoleTextAttribute(hout, 12);SetPosition(posx, posy + 1);cout << "▽";head++;q[head].x = posx;q[head].y = posy + 1;q[head].next = Last;if ((q[head].x == MAXSIZE - 3) && (q[head].y == MAXSIZE - 2)) {break;}}//每走四个方向,即遍历一次;让last++;第一个数出队列,让队列的第二个数开始向上下左右进行搜索Sleep(10);//让尾指针上移;证明出队列;Last++;}ClearMap(map);SetConsoleTextAttribute(hout, 4);printfMap(map);SetConsoleTextAttribute(hout, 14);PrintMenu();while (Last != -1) { //当Last遍历到-1的时候,证明已经到了队列的尾部SetPosition(q[Last].x, q[Last].y);SetConsoleTextAttribute(hout, 4);Sleep(10);cout << "◆";SetConsoleTextAttribute(hout, 14);Last = q[Last].next;}
}//指定位置删除墙
void deleteWall(int **map){SetConsoleTextAttribute(hout, 13);SetPosition(48, MAXSIZE + 3);cout<<"请输入需要删除墙壁的下标: ";int x,y;//SetPosition(46, MAXSIZE + 5);cin>>x>>y;if(map[x][y] ==WALL && x<MAXSIZE && y<MAXSIZE) //{map[x][y] = ROAD;} SetConsoleTextAttribute(hout, 14);
}//指定位置添加墙
void addWall(int **map){SetConsoleTextAttribute(hout, 13);SetPosition(48, MAXSIZE + 3);cout<<"请输入需要添加墙壁的下标: ";int x,y;cin>>x>>y;if(map[x][y] ==ROAD && x<MAXSIZE && y<MAXSIZE) //{map[x][y] = WALL ;} SetConsoleTextAttribute(hout, 14);} void welcome_01(){char heart[30][150]={" ************ ************"," ****************** ******************"," ******************#******* **************************"," **********************#********* ********************************"," **********************##########*** **************#******************** "," **********************#*********#**** **##********#************************ "," *********##########**#****#****#**********##****#************************** "," **********#*******#*#*****#***#***************#********#########*********** "," **********#*****#********#***********#####***#********#*******#********** "," ***********#***#********#***************#***#******#*#****#**#********* "," ***********##**********#**************#*****#****#***#*****#*#******* "," **********##*********#*#************#*****####*****#*******#******* "," ********#**#*******#***#************#*************#************** "," *****#****#*****#*****#************#************#************ "," **#**********#*******#******######************#********** "," **********#*********#*****########################### "," ************************************************** "," ********************************************** "," ****************************************** "," ************************************** "," ********************************** "," ****************************** "," ************************** "," ********************** "," ****************** "," ************** "," ********** "," ****** "," ** "};int i;SetConsoleTextAttribute(hout, 11);for(i=0;i<29;i++) //逐行打印printf("%s\n",heart[i]);Sleep(1000);system("cls");
}void End_designer(){system("cls");SetConsoleTextAttribute(hout, 11);printf("\n\n\t\t☆☆☆☆☆☆☆☆★★设计者信息★★☆☆☆☆☆☆☆☆\n\n");printf("\t\t☆☆☆ 迷宫小游戏 ☆☆☆\n\n");printf("\t\t●● 班级：XX计科一班 ●●\n\n");printf("\t\t●● 成员：小张 210912XXX ●●\n\n");printf("\t\t●● 成员：小潘 210912XXX ●●\n\n");printf("\t\t●● 成员：小郭 210912XXX ●●\n\n");printf("\t\t●● 成员：小吴 210912XXX ●●\n\n");//printf("\t\t●● ●●\n\n");printf("\t\t●● 谢谢大家的观看 ●●\n\n");printf("\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
}
int main() {ChangeConsoleSize(51, 75); //改变控制台窗口大小srand((unsigned)time(NULL));int **map = NULL;bool flag = false;map = getMap();//创建基础地图//根据基础地图创建迷宫地图createMap(map, 2, 2);//使用深度优先,创建地图setIn_OutMap(map);//设置外围(其他)Road位置welcome_01();Welcome();//运行程序后的显示界面SetConsoleTextAttribute(hout, 6);//一个API设置字体颜色和背景色函数printfMap(map);//显示地图样貌PrintMenu();//显示菜单——位于迷宫的右侧while (1) {switch (getch()) {case 'a':DepthFirstSearch(map);//深度优先搜索-出迷宫break;case 'b':map[2][1] = WALL;//map[MAXSIZE - 3][MAXSIZE - 2] = WALL;// MAP[MAXSIZE - ][] = ROAD;WidthFirstSearch(map);//广度优先搜索出迷宫break;case 'c':
// recursionSearch(map,2,2);//递归搜索break;case 'd':ClearMap(map);//清空地图printfMap(map);//显示地图PrintMenu();//显示菜单break;case 'e':map = getMap();createMap(map, 2, 2);setIn_OutMap(map);printfMap(map);PrintMenu();break;case 'f':ClearMap(map);//清空地图addWall(map); printfMap(map);//显示地图PrintMenu();//显示菜单break;case 'g':ClearMap(map);//清空地图deleteWall(map);printfMap(map);//显示地图PrintMenu();//显示菜单break; case 'h':flag = true;break;default:break;}if (flag) {system("cls");//SetPosition(15, 30);End_designer();//cout << "~~~ByeBye~~~";Sleep(1000);break;}}return 0;
}// MAP[MAXSIZE - ][] = ROAD;WidthFirstSearch(map);//广度优先搜索出迷宫break;case 'c':
// recursionSearch(map,2,2);//递归搜索break;case 'd':ClearMap(map);//清空地图printfMap(map);//显示地图PrintMenu();//显示菜单break;case 'e':map = getMap();createMap(map, 2, 2);setIn_OutMap(map);printfMap(map);PrintMenu();break;case 'f':ClearMap(map);//清空地图addWall(map); printfMap(map);//显示地图PrintMenu();//显示菜单break;case 'g':ClearMap(map);//清空地图deleteWall(map);printfMap(map);//显示地图PrintMenu();//显示菜单break; case 'h':flag = true;break;default:break;}if (flag) {system("cls");//SetPosition(15, 30);End_designer();//cout << "~~~ByeBye~~~";Sleep(1000);break;}}return 0;}
