设计要求

       生成类似如图n行m列的迷宫，起点为（2，1），终点为（n-1，m），用C/C++原因设计自动寻路算法并可视化寻路过程。

基础功能：生成随机迷宫/从文件读取迷宫/自动寻路

进阶：寻找最最短路径/手动操控迷宫/带有怪物的迷宫/含有倒计时的迷宫

底层数据结构

       迷宫最重要的是地图，我们存一个int Map[N][N]数组，表示迷宫在Map[i][j]表示i行j列是什么，我让i和j从1开始，最左上角是(1,1)，第二行第一个是(2,1),第一行第二个是(1,2)，以此类推，当然你也可以从0开始。

       在程序开头对不同物品进行宏定义可以增强程序可读性，当然也可以用枚举类型。我的上下左右定义的数字和方向数组下标相同，进一步简化程序。

生成迷宫（kruskal最小生成树）

        如图，令红点永远为墙，白点永远为路，当然还要初始化起点终点。蓝点为可能存在的边，抽象为一张网格图，给每条边加上随机的边权，用最小生成树算法打通蓝边，可以在最后再随机额外打通几条边。这样虽然不能生成某些类型的地图，但是容易实现并且地图美观，还不会产生大量道路聚集的区块。代码较长，可以在最后完整代码的random_map()函数里看

打印地图

我们需要用到一些不常见函数，比如隐藏光标，移动光标，清空命令行现实内容等。

注意打印地图的时候不要每次都全清空，不然会闪烁，也不要每次全打印，否则输出耗时过久，我用了putchar输出优化，但是最重要的还是每次打印只在有变化的地方修改，建议写一个在你的坐标(x,y)处打印的函数，计算好你的坐标如何调整到命令行光标坐标

自动寻路（dfs）

        主要用到递归回溯的方法，如果走到终点就结束递归，如果回溯，说明后面的路线均为死路，要把地图标记为Fail，注意递归和回溯的时候都需要打印地图，另外打印地图前一定要用Sleep(100)函数暂停100毫秒，可以很好地显示过程，不然一瞬间就跑完了。具体dfs不细讲了，如果无法理解的话可以找点视频或者问问身边的大神。

        这里用到一个重要技巧，就是方向数组枚举四个方向，主要枚举四个方向的时候一定要判断下一个点是否合法，在之后任何需要移动的地方，都要记得判断！

我这里输出“Me”物件的代码位置可以微调，来改变结束时，终点处打印的是"End"还是“Me”

手动迷宫

主要用到了读取键盘的函数，注意读取上下左右键的时候回读到两个量，其中第一个应该忽略，因此我写了自己的读取键盘函数。在读键盘之前清空缓冲区，可以有效避免之前额外按键的影响，比如你想实现一个结束后按任意键继续，但是你在看它自动走的时候随便按了下键盘，等他走完之后，就任意键继续的功能就会受到影响。                                                           getch()是读取键盘按键，在下图头文件中

主要程序可以用一个while(还未到终点)继续走;来实现，读取键盘的时候，如果读到合法按键，就产生功能，上下左右方向键的值可以在我的代码里面看。你也可以加入额外功能，比如esc退出，r重玩，z撤销......

最短路径

       主要用了bfs，用队列来实现广度优先搜索，每个点只入队列一次，设点数有N=n*m个，则时间复杂度为O(N)。同样如果不了解bfs的话建议自学一下，dfs和bfs都是计算机专业重要基础算法。

       记录路径的话可以用到类似dijstra最短路的方法，更新下一个点的时候记录前驱predecessor，注意到前驱数组是一个二维的点到二维的点的映射，可以开一个二维的pair<int,int>数组，如果是C语言，可以写一个结构体Pair，然后开一个结构体数组。

       记录完前驱之后需要从终点一直沿着前驱倒退回到起点，并在地图上记录上一个点到这个点的方向是什么。

       最后再从起点开始走，如果枚举四个方向，沿着已经被标记过方向的路线一遍打印一遍走到终点。

怪物游走

        由于存在怪物，之前生成的迷宫很难走通，因此我只允许从文件读入怪物地图。

        这里需要用到计时函数以及键盘按下事件，怪物每过多少时间动一次，循环记录时间的同时检测是否有按键按下，如果有，则读取一个，这里不要清空缓冲区，不然会不太灵敏，我也不清楚为什么。每次移动完之后需要判断你和怪物是否相邻/重合。

这里还要附上怪物迷宫地图，我也没有仔细设计可玩性较强的地图，就随便整了两个。

完整代码

       到这里，主要的内容已经讲完了，我们还需要设计Menu界面来完善功能，我写这个程序只花了一天，大概6小时，就做的不是很完善，可能还有不少bug，欢迎大家发现我的bug，也可以补充更多的内容。最后附上完整源代码。

感谢大家阅读！