在阅读数据结构与算法第八章时，我读到了如何使用不相交集的思想来生成一个迷宫，可惜的是，书中并没有给出具体代码，我花了大概一个下午的时间实现了一个简易版本的。
生成迷宫的算法描述如下：首先我们将地图看成许多小房间，我们不断打通其中一些墙壁，然后检查第一个和最后一个小房间是否是一个等价类（即它们是否有一个祖先），如果不是，我们继续砸墙。其中遇到了一些有趣的问题我在注释中写出来了。
上手的第一个难点是如何打印地图——是的，这是一个很难的问题（严肃脸），因为我不想这么一个简单程序大动干戈的去使用图形库，最后的效果还有些差强人意，不过勉强可以接受。
第二个问题是如何打通一面墙，打通自然将wallmap相应的设为false就可以了，问题是我们如何找到相邻的墙呢？很自然的，这个问题的解决办法我们可以想到先随机选择一个房间，然后探查它周围相邻房间的数量，再从中随即选择一个。容易发现只有位于i=1,i=2*N-1,j=1,j=2*N-1这两行两列的房间少于四个邻居房间。
但是为了更快的看到效果，我的选择是——不解决这个问题哈哈哈。遇到打不通的房间我就直接下一次循环，迟早能随机到可以打通的哈哈哈哈笑死我了这个想法——等我有心思了我就把它改过来，我保证。地图的创建也有这种破罐子破摔的做法，里面有许多用不到的空间，不过考虑到bool类型只占有1字节，哪怕50*50的地图也不会浪费超过1kb的内存，所以这是可以接受的。——而直接下一次循环的做法时间上感觉是不可以接受的，因为也许会随机到天荒地老，但是如果不打印中间过程信息，生成一个20*20的迷宫在我的电脑上仅花费不超过0.2秒，所以考虑到代码的简洁性，我就先这么着了。
话不多说了，上代码。
#include <iostream>
#include <vector>
#include <random>
using namespace std;
#define N 20
class DisjSets {
public:
DisjSets(int num) {
for (int i = 0; i < num; i++) {
s.push_back(-1);//初始化不相交集类，大家都没有祖先
}
}
int find(int x) {
if (s[x] < 0) return x;
else return s[x] = find(s[x]); //更新先祖
}
void unionSets(int r1, int r2)//我们必须确保输入的是先祖，这是必须的
{
if (s[r2] < s[r1])
s[r1] = r2; //s2更深成为祖先
else {
if (s[r1] == s[r2])
--s[r1];//更新高度，说深度也许更好
s[r2] = r1;
}
}
bool connect(int x, int y) {
// cout << find(x) << ' ' << find(y) << endl;
return find(x) == find(y);
}
private:
vector<int> s;
};
void print(bool wallmap[][N * 2 + 1]) {
for (int i = 0; i <= N * 2; i++) {
if (i == 0 || i == N * 2) { //处理首行和末行
for (int j = 0; j <= N * 2; j++) {
if (i == 2 * N && (j == 2 * N - 1 || j == 2 * N)) {
printf(" ");
continue;
}
printf("■");
}
printf("\n");
continue;
}
for (int j = 0; j <= N * 2; j++) {
if (i == 2 * N - 1 && j == 2 * N) {
printf(" ");
continue;
}
if (j == 0 || j == N * 2) { //单独处理第一列和最后一列
printf("■");
} else {
if (wallmap[i][j]) {
printf("■");
} else {
printf(" ");
}
}
}
printf("\n");
}
}
void initialmap(bool wallmap[][N * 2 + 1]) {
for (int i = 0; i < N * 2 + 1; i++)
for (int j = 0; j < N * 2 + 1; j++)
wallmap[i][j] = true;
for (int i = 1; i < 2 * N; i += 2) { //小房间里面肯定没有墙
for (int j = 1; j < 2 * N; j += 2)
wallmap[i][j] = false;
}
}
bool destroywall(int n1, int n2, bool wallmap[][N * 2 + 1]) {
if(n1%N==0&&n2+1==n1) return false;
if(n2%N==0&&n2-1==n1) return false;
int i = (n1 / N) * 2 + 1; //得到n1坐标
int j = (n1 - (n1 / N) * N) * 2 + 1;
// cout<<i<<j<<endl;
if (n2 - n1 == 1 || n1 - n2 == 1) { //得到具体墙的位置
j += n2 - n1;
} else if (n2 - n1 == N || n1 - n2 == N) {
i += (n2 - n1) / N;
} else return false; //如果遇到不能打通的就退出呗
// cout<<i<<j<<endl;
wallmap[i][j] = false;
return true;
}
void printset(DisjSets &room)
{
for(int i=0;i<N*N;i++)
{
cout<<i<<":"<<room.find(i)<<' ';
}
cout<<endl;
}
int main() {
bool wallmap[N * 2 + 1][N * 2 + 1]; //N*N的迷宫需要2N+1大的地图
initialmap(wallmap);
// print(wallmap);
DisjSets room(N * N); //创建一个不相交集类
default_random_engine e;
e.seed(time(0));
uniform_int_distribution u(0, N * N - 1);
while(!room.connect(0,N*N-1))
{
int a=u(e);
int b=u(e);
if(destroywall(a,b,wallmap))
{
// cout<<room.find(a)<<' '<<room.find(b)<<endl;
if(room.find(a)==room.find(b)) continue;//相等会无限递归,这真是一个难以发现的bug
room.unionSets(room.find(a),room.find(b));//我们必须确保合并等价类的是先祖，想想看这是为什么
// printset(room);
// print(wallmap);
}
}
print(wallmap);
}