主要用到了 求并/查找 数据结构,这个结构封装在类DisjSets中。这个结构用于区分等价关系,即将一个集合分为多个等价的子集,然后可以对子集求并,或者查找某一元素所属的子集。基本操作很简单,即union和find两种。
生成迷宫的算法是从各处的墙壁开始(入口和出口除外),不断随机选择一面墙,如果被墙分隔的单元不连通,就拆掉该墙,重复此过程直到开始单元和终止单元连通。入口位于左上角,出口位于右下角。
以下是算法运行生成的某个10阶迷宫:
代码如下:
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#define N 10
using namespace std;
int wall_row[N+1][N];
int wall_col[N][N+1];
class DisjSets
{
public:
explicit DisjSets(int numElements);
int find(int x) const;
void unionSets(int node1, int node2);
bool connected(int node1, int node2) const
{
return find(node1) == find(node2);
}
private:
vector<int> s;
};
DisjSets::DisjSets(int numElements):s(numElements)
{
for (int i = 0; i < s.size(); i++)
s[i] = -1;
}
int DisjSets::find(int x) const
{
if (s[x] < 0)
return x;
else
return find(s[x]);
}
void DisjSets::unionSets(int node1, int node2)
{
int root1 = find(node1);
int root2= find(node2);
if (root1==root2)
return;
if (s[root2] < s[root1])
s[root1] = root2;
else {
if (s[root1] == s[root2])
s[root1]--;
s[root2] = root1;
}
}
void fill(int value)
{
for (int i = 0; i < N+1; i++)
for (int j = 0; j < N; j++)
wall_row[i][j] = value;
for (int i = 0; i < N; i++)
for (int j = 0; j < N+1; j++)
wall_col[i][j] = value;
}
void print()
{
int i, j;
for (i = 0; i < N+1; i++) {
for (j = 0; j < N+1; j++) {
if (i > 0)
if (wall_col[i-1][j])
cout << "|";
else
cout << " ";
if (j < N)
if (i > 0)
if (wall_row[i][j])
cout << "_";
else
cout << " ";
else
if (wall_row[i][j])
cout << " _";
else
cout << " ";
}
cout << endl;
}
}
void map_rand(int x, int &type, int &a, int &b)
{
type = 0;
if (x >= N*(N-1)) type = 1;
if (type == 0) {
a = x / (N - 1);
b = x % (N - 1) + 1;
} else {
x -= N*(N-1);
a = x / N + 1;
b = x % N;
}
}
void map_pos(int type, int a, int b, int &node1, int &node2)
{
if (type == 0) {
node1 = a * N + b - 1;
node2 = a * N + b;
} else {
node1 = (a - 1) * N + b;
node2 = (a - 1) * N + b + N;
}
}
int randselect(void)
{
int range = N*(N-1)*2;
return rand() % range;
}
int main()
{
fill(1);
srand(time(0));
wall_row[0][0] = 0;
wall_col[0][0] = 0;
wall_row[N][N-1] = 0;
wall_col[N-1][N] = 0;
// print();
int amount = N * N;
DisjSets s(amount);
while (!s.connected(0, amount-1)) {
int type, a, b;
do {
int wall = randselect();
map_rand(wall, type, a, b);
} while ((type == 0 && wall_col[a][b] == 0) ||
(type == 1 && wall_row[a][b] == 0));
int node1, node2;
map_pos(type, a, b, node1, node2);
if (!s.connected(node1, node2)) {
if (type == 0)
wall_col[a][b] = 0;
else
wall_row[a][b] = 0;
s.unionSets(node1, node2);
}
}
print();
return 0;
}
- 大小: 10.5 KB
分享到:
相关推荐
使用Java编写的迷宫游戏,游戏人物为仙剑98中的李逍遥造型。 程序可以生成任意大小的迷宫,迷宫采用合并不相交集类方法生成。
功能介绍:根据不相交集原理随机生成迷宫并查找其路径,输出迷宫的数字及图文信息及带路径的图文信息(含文件操作) 设计时间:2010.3.20 测试平台:XP/VC++ 6.0及以上 BY 法官*/ 注:我写的这个是根据数据结构里的不相...
生成迷宫一个简单的算法是从各处的墙壁开始。此时,我们不断地随机选择一墙面,如果该墙分割的单元彼此不连通,那么就拆掉这面墙。如果重复这个过程直到开始单元和终止单元连通,那么就得到一个迷宫。
利用不相交集类生成任意大小的迷宫,并且利用等高线算求解迷宫的最优解。最后利用win32画出结果。程序适合电脑鼠初学者学习迷宫算法。
迷宫游戏的Java实现-合并不相交集类方法生成大迷宫(源文件) 唯一的遗憾是当初没有使用多线程机制 :-) 生成之后的界面是李逍遥走迷宫的游戏,可以调整视野大小等。 我的资源中可以下到该项目的jar包(0资源分)
算法设计技巧与分析:第四讲 堆和不相交集数据结构.ppt
迷宫 利用不相交集生成指定行和列尺寸的迷宫。
利用C++实现不相交集类
C#,图论与图算法,无向图(Graph)回环(Cycle)的不相交集(disjoint)或并集查找(union find)判别算法与源代码 不相交集数据结构是一种数据结构,它跟踪划分为多个不相交(非重叠)子集的一组元素。联合查找...
这是数据结构课程中,不相交集这一章的ppt.具体介绍了很多相关内容,可供大家参考使用。
设 A={a1,a2,…,an}, B={b1,b2,…,bn}是整数集合,其中 m=O(log n)。要求设计一个算法求集 合 C=A∩B。提示:使用二分查找技术。
数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 ...
c语言数据结构关于迷宫的问题,很不错哦、
针对各种传统可视外壳生成算法中数据冗余、精确度低、健壮性不足等问题, 提出了一种新的可视外壳生成算法,即采用加权线段求交、线段集合中心线性过滤、多边形边界检测等方法重建物体模型。与传统方法相比,本算法...
(空间搜索外包矩形常用算法) 2. 包含与被包含,也是通过两个矩形的X最大值,最小值以及Y最大值,最小值的大小比较判定。(空间搜索外包矩形常用算法) 3. 相交。相交情况比较复杂,情况分以下三种
java 二个数组的交集,算法 java 二个数组的交集,算法
求交集和非交集 求交集和非交集 求交集和非交集
问题规范:该程序将使用以下算法自动生成一个随机迷宫:将迷宫视作一个单元格网格,其中每个单元格都由四面围成的墙包围,该四面墙将其与所有相邻单元格分隔开。 随机选择分隔两个单元的墙,如果迷宫中的路径尚未...
不相交集