月度归档:2015年01月

矩阵迷宫生成算法

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

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

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

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

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

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

#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

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

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

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

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)。迷宫通路较为曲折,下面是用深搜获得的解。

迷宫,解

 

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