C语言的迷宫游戏.doc

嗯... 其实也没啥... 随便敲了一段程序..
先上效果图:

其实 随机化 Kruskal 来搞迷宫程序也是很正常..
相比 DFS 这种危险的东西而言要好得多了..
/* ----------------------------------------------
就是求一个 随机生成树的问题..
思路就是 :
假如把 每个空格看成一个点. 空格与空格之间的墙壁看成一条边.
那么初始的迷宫就是一个无向图 G = <V , E>

然后我要使得入口和出口要联通.
相当于去搞一个图G 的导出子图, 使得子图中的顶点 E 和顶点 S 是联通的.

有点算法功底的人应该想到对于DFS这种东西...实在是害怕栈溢出... 你有本事就改成非递归形式.. 但估计没人有本事. 还不如用生成树的思路做.

算法步骤：
1）随机选择 G 中的一条边 e ∈ E , 判断 e 连接的两个顶点是否在同一集盒 ,
如果不是, 将两个顶点所在集盒合并, 并且把墙擦掉 ;
反之 , 进入 2)

2) E = E - {e} ; //从边集中去掉元素 e

3) 如果 E = Φ (空集) , 结束算法 ; 反之 , 转到 1)

这其中的 判断两个顶点在同一集盒 以及 将两顶点合并 如果要高效率的操作的话.
仅仅用线性表是肯定会**的.. 这里用数据结构里常用的树来存储.
即 所谓的 UFS(Union_Find_Set) 并查集.
这个数据结构我已经手写成了类 , 放在了源代码中.
还有迷宫地图相关的操作函数以及变量全部放在了命名空间 Maze 中,不然冲突的太严重了.

另外: 命名空间 std 我并没有完全开放 , 这也是给新手一种示范 。 告诉C++初学者,别为了偷懒就随便的全局 "using namespace std;" , 大项目中的后果是很坑爹的....

(源代码整理后以图片形式贴出)
///////////// 这帖子在代码全部贴出前尽量别插楼(谢谢大家的配合) /////////////

8

8

最后附上使用的std
std::list
std::pair
std::cin
std::cout
std::endl