本文共 13553 字，大约阅读时间需要 45 分钟。

数据结构大作业–迷宫问题

上图：

代码有详细注解

迷宫自动生成问题单独讨论

当然由于出口随机的原因右小概率会出现bug(这无伤大雅)

首先我们都知道，迷宫只有一条正确的道路。

这个时候请把自己想象成一只地鼠，要在这个区域不停的挖，直到任何一块区域再挖就会挖穿了为止。

我们挖的道路就像树结构，树上有很多的分支，分支也有子分支，每个子分支都不能相交，相交了就说明墙被挖穿了，那么此时的迷宫就可能存在多条正确道路，这不是我们想看到的。

那么基于唯一道路的原则，我们向某个方向挖一块新的区域时，要先判断新区域是否有挖穿的可能，如果可能挖穿要立即停止并换个方向再挖。如图：

版权声明：迷宫随机生成参照其他博主

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define WALL 0#define ROAD 1#define MAXSIZE 44#define ARRIVEROAD 2using 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) { 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)成立,则证明 行 与 列 其中必有一个为posx或posy 而这有对应当前路径前面那面墙上下左右四种情况; 若map[j][k] == ROAD成立,则证明该已经是路径(当前路径前面的墙的上下左右某一个方向已经是路径); 那就没必要挖墙了; 因为这会造成地图挖穿,或者形成回路;或者二叉树分支相互通(将地图看成二叉树) */ int 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); } }}
        
       
      
     
    
   

这里是全部代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define WALL 0#define ROAD 1#define MAXSIZE 44#define ARRIVEROAD 2using 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) { 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)成立,则证明 行 与 列 其中必有一个为posx或posy 而这有对应当前路径前面那面墙上下左右四种情况; 若map[j][k] == ROAD成立,则证明该已经是路径(当前路径前面的墙的上下左右某一个方向已经是路径); 那就没必要挖墙了; 因为这会造成地图挖穿,或者形成回路;或者二叉树分支相互通(将地图看成二叉树) */ int 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(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
         
          }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 << "出版商：4399"; SetPosition(4, 16); cout << "侵权必究"; SetPosition(10, 20); cout << " 欢迎来您到迷宫游戏1.10.4 " << endl; SetPosition(14, 10); cout << "玩命加载中 : "; for (int i = 0; i < 80; ++i) { Sleep(30); printf("+"); } system("cls"); SetPosition(10, 20); cout << " 祝你游戏愉快~~~~ "; Sleep(1000);}//这个代码网上学的void PrintMenu() { SetConsoleTextAttribute(hout, 11); SetPosition(4, MAXSIZE + 5); cout << "■■■■■■■■操作介绍■■■■■■■■"; SetPosition(6, MAXSIZE + 5); cout << " 按 a 进行深度优先搜演示"; SetPosition(8, MAXSIZE + 5); cout << " 按 b 进行广度优先搜演示"; SetPosition(10, MAXSIZE + 5); cout << " 按 c 进行递归搜索演示"; SetPosition(12, MAXSIZE + 5); cout << " 按 d 去除所有路径"; SetPosition(14, MAXSIZE + 5); cout << " 按 e 重新生成迷宫"; SetPosition(16, MAXSIZE + 5); cout << " 按 f 退出迷宫游戏"; SetPosition(18, MAXSIZE + 5); cout << "(手动搜索路径正在维护中,更多详细信息请关注"; SetPosition(19, MAXSIZE + 5); SetConsoleTextAttribute(hout, 4); cout << " <
          
           > "; SetConsoleTextAttribute(hout, 11); SetPosition(20, MAXSIZE + 5); cout << "■■■■■■■■游戏介绍■■■■■■■■"; SetPosition(22, MAXSIZE + 5); cout << " 本游戏有学长大力赞助,经过三天"; SetPosition(24, MAXSIZE + 5); cout << " 不眠之夜的开发,于2021.4.30正式验收"; SetPosition(26, MAXSIZE + 5); cout << " 游戏演示了经典迷宫问题,使用prim---"; SetPosition(28, MAXSIZE + 5); cout << " 最小生成树算法,随机自动生成迷宫,"; SetPosition(30, MAXSIZE + 5); cout << " 使用了三种遍历方式 :"; SetPosition(32, MAXSIZE + 5); cout << " 1.递归遍历-RC"; SetPosition(34, MAXSIZE + 5); cout << " 2.深度优先-DFS"; SetPosition(36, MAXSIZE + 5); cout << " 3.广度优先-BFS"; SetPosition(38, MAXSIZE + 5); cout << "X -- 表示死路"; SetPosition(40, MAXSIZE + 5); cout << "▽-- 小球走过的路径"; SetPosition(42, MAXSIZE + 5); 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 //使所有的递归方法(由于多次调用setWay方法,在栈中有好多setWay方法,每个都相互独立) //的四个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;//标记这个方向,证明已经走过了： SetPosition(posx - 1, posy); cout << "▽"; //让当前位置的这个方向入队列,并让头指针++; head++; //当前位置信息入队列; q[head].x = posx - 1; q[head].y = posy; //让Queue指向下一个; 第一次指向 -1 q[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;//标记这个方向,证明已经走过了： SetPosition(posx + 1, posy); cout << "▽"; head++; q[head].x = posx + 1; q[head].y = posy; q[head].next = Last;//指向下一个;第一个指向 - 1 if ((q[head].x == MAXSIZE - 3) && (q[head].y == MAXSIZE - 2)) { break; } } if (map[posx][posy - 1] == ROAD) { map[posx][posy - 1] = ARRIVEROAD;//标记这个方向,证明已经走过了： 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;//标记这个方向,证明已经走过了： 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; }}int main() { ChangeConsoleSize(45, 70); srand((unsigned)time(NULL)); int **map = NULL; bool flag = false; map = getMap(); //根据基础地图创建迷宫地图 createMap(map, 2, 2); setIn_OutMap(map); Welcome(); SetConsoleTextAttribute(hout, 6); 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': flag = true; break; default: break; } if (flag) { system("cls"); SetPosition(15, 30); cout << "ByeBye~~~"; Sleep(1000); break; } } return 0;}