Fun

矩阵迷宫生成算法

脑残的数据结构课设要做个什么脑残的非递归迷宫问题求解。最脑残的是还让自己去生成一个迷宫。于是有了这篇文章。

言归正传。先介绍一个神奇的数据结构叫“并茶几” 哦不，“并查集”。并查集是一中用于判断元素是否属于同一集合的数据结构，主要的操作有查找和合并。并查集实际上是一个森林，每一个集合是一棵树。

在并查集中，默认每个元素的父元素指向自己，在执行合并操作的时候只需要将自己的父元素指向要合并的节点，即可完成合并。在执行查找的时候，只需要一直寻找父元素，直到父元素指向父元素本身。

但是当合并次数增多以后，可能会出现树的深度过大，导致每次回溯父节点耗时过长。这里有一种路径压缩的办法。在执行find的时候，将每个节点的父节点都改为最远处的父节点。在递归执行查找的时候只需要很小的改动即可。

还有一种按秩合并的算法可以优化并查集。但是远没有路径压缩简单易懂，在小规模数据时无需使用。

下面提供了一个简单封装过的并查集类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#ifndef _UNIONSET_H_
#define _UNIONSET_H_
#include <vector>
class UnionSet
{
private:
    std::vector<int> Fa;
public:
    UnionSet(){}
    void Init(int n)
    {
        for (int i = Fa.size(); i <= n; ++i)
            Fa.push_back(i);
    }
    int Find(int u)
    {
        if (Fa.size() <= u)
            Init(u);
        while (u != Fa[u])
            return Fa[u] = Find(Fa[u]);
        return u;
    }
    bool Same(int x, int y)
    {
        return (Find(x) == Find(y));
    }
    int Merge(int x, int y)
    {
        x = Find(x);
        y = Find(y);
        Fa[y] = x;
        return x;
    }
    int MakeEmpty()
    {
        for (int i = 0; i < Fa.size(); ++i)
            Fa[i] = i;
    }
};

#endif

说完了并查集就该让我们谈谈怎么去生成迷宫了。

迷宫实质上就是从原点到重点的一科生成树，生成树中的所有节点必属于同一个集合。于是借助并查集和随机数构造迷宫。

在生成迷宫时，我们随机选择一堵墙，并把墙打通，隔开的两个格子在并查集中合并。直到原点和终点在同一个集合中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

vector<vector<int>> *map = nullptr;
vector<vector<bool>> *visit = nullptr;
const int LocX[4] = { 0, 1, 0, -1 };
const int LocY[4] = { 1, 0, -1, 0 };
enum Direction    { UP, RIGHT, DOWN, LEFT };
struct Point
{
    int x, y;
};
void RamdomMap(int x, int y)
{
    system("cls");
    if (map != nullptr)
        delete map;
    map = new vector<vector<int>>(y*2 + 2, vector<int>(x*2 + 2, '0'));
    vector<vector<int>> &map = *::map;
    UnionSet us;
    int maxm = x*y;
    while (us.Find(1)!=us.Find(maxm))
    {
        int rx = (rand() % x)+1;
        int ry = (rand() % y)+1;
        rx = rx * 2 - 1;
        ry = ry * 2 - 1;
        int loc = rand() % 4;
        if ((ry + LocY[loc]<1 || ry + LocY[loc] > y*2-1) || (rx + LocX[loc]<1 || rx + LocX[loc] > x*2-1))
            continue;
        rx += LocX[loc];
        ry += LocY[loc];
        if (ry % 2 == 0)
        {
            int tx1 = rx / 2 + 1, tx2 = tx1;
            int ty1 = ry / 2, ty2 = ry / 2 + 1;
            if (us.Find((ty1 - 1)*x + tx1) == us.Find((ty2 - 1)*x + tx2))
                continue;
            map[ry][rx] = '1';
            map[ry - 1][rx] = '1';
            map[ry + 1][rx] = '1';

            us.Merge((ty1 - 1)*x + tx1, (ty2 - 1)*x + tx2);
        }
        else
        {
            int ty1 = (ry + 1) / 2, ty2 = ty1;
            int tx1 = rx / 2, tx2 = rx / 2 + 1;
            if (us.Find((ty1 - 1)*x + tx1) == us.Find((ty2 - 1)*x + tx2))
                continue;
            map[ry][rx] = '1';
            map[ry][rx - 1] = '1';
            map[ry][rx + 1] = '1';

            us.Merge((ty1 - 1)*x + tx1, (ty2 - 1)*x + tx2);
        }
        COORD pos = { 0, 0 };
        SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);
        for (int j = 1; j < y*2 ; ++j)
        {
            for (int i = 1; i < x*2; ++i)
            {
                printf("%c", map[j][i]);
            }
            printf("n");
        }
        //printf("正在点(%d,%d)ttn", rx, ry);

    }
    
    FILE *fp = fopen("maze.map", "w");
    fprintf(fp,"%d %dn", x * 2 - 1, y * 2 - 1);
    for (int j = 1; j < y*2; ++j)
    {
        for (int i = 1; i < x*2; ++i)
        {
            fprintf(fp,"%c ", map[j][i]);
        }
        fprintf(fp, "n");
    }
    fclose(fp);
    delete ::map;
    ::map = nullptr;
}

以上就是用这种方法生成的迷宫矩阵。原点为（0，0），终点为（15，15）。迷宫通路较为曲折，下面是用深搜获得的解。

这个生成算法有个缺点，因为相邻的两个点之间必有墙，所以只能生成奇数乘奇数的矩阵。如果有能生成偶数矩阵的算法，欢迎在下面留言讨论。