[C++] 实现迷宫生成算法 采用了并查集数据结构
随机生成一个迷宫，一般这种问题要用并查集的，但是具体算法我没有上网查找过，所以自己想了一个，但是我的想法还不成熟，存在很多缺陷，望大牛们指正。算法的思想是：
while( 入口和出口 不通)
{
....随机找个点 -> (x,y)
....随机找个方向->上/下/左/右 -> dx,dy = {0,1,-1}
....如果(x,y)和( x + dx , y + dy)有一个是墙
.........把墙去掉
.........联通(x,y) 和 (x+dx,y+dy)
}
如果 RP是负无穷的话，可能要搜很长时间。。。。
/*
* Auther:Knuth学徒
* Lang:C++
* Date:2011-2-12
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
using namespace std;
const int M = 5;
const int N = 5;
const int direction = {(0,-1),(0,1),(-1,0),(1,0)};
int father; //并查集的父节点记录数组
int map; //地图数组
/////////////////////////////////////////////////
// 函数名：hash
// 参数：横坐标和纵坐标以及棋盘的列大小
// 前提：None
// 返回：坐标的散列值
/////////////////////////////////////////////////
int hash(int x,int y, int col)
{
return ( x * col + y );
}
/////////////////////////////////////////////////
// 函数名：id
// 参数：点的散列值，存在a和b中
// 前提：None
// 返回：引用传值回去
/////////////////////////////////////////////////
void id(int val, int &a,int &b)
{
a = val/M;
b = val%M;
}
/////////////////////////////////////////////////
// 函数名：Make
// 参数：None
// 前提：None
// 返回：None
// 描述：并查集的初始化过程
/////////////////////////////////////////////////
void Make()
{
for(int i=0;i<N;++i)
for(int j = 0;j<M;++j)
{
father = hash(i,j,M);
// printf("f[%d] = %d ",hash(i,j,M),father);
}
}
/////////////////////////////////////////////////
// 函数名：FindSet
// 参数：节点X表示某个点的散列值
// 前提：None
// 返回：节点x的祖先
// 描述：递归时采用了路径压缩
/////////////////////////////////////////////////
int FindSet(int x)
{
if( x != father)
{
father = FindSet(x);
}
return father;
}
/////////////////////////////////////////////////
// 函数名：Union
// 参数：两个散列值
// 前提：None
// 返回：None
// 描述：合并两个集合
/////////////////////////////////////////////////
void Union(int a,int b)
{
father = b;
}
int main()
{
Make();
int sx,sy,ex,ey;
srand((unsigned)time(0));
int a = rand() % M*N; //入口
int b = rand() % M*N;//出口
id(a,sx,sy);
id(b,ex,ey);
map = map = 0;
// cout<<"a = "<<a<<endl;
// cout<<"b = "<<b<<endl;
//cout<<"f="<<father<<endl;
//cout<<"fb="<<father<<endl;
while(FindSet(a) != FindSet(b))
//如果入口和出口不联通
{
int tmp = rand() % M*N;
//随机选一点
int dire = rand()%4;
int tx,ty,ttx,tty;
id(tmp,tx,ty);
// printf("%d %d",tx,ty);
ttx = tx + direction;
tty = ty + direction;
if(map || map)
{
map = (map == 1 ? 0:0);
map = (map == 1 ? 0:0);
Union(hash(tx,ty,M),hash(ttx,tty,M));
}
}
// cout<<"OK2"<<endl;
for(int m = 0;m<N;++m)
{
for(int n =0;n<M;++n)
{
printf("%d",map);
}
printf("\n");
}
return 0;
} 好东西,收藏了 看着 好复杂呀 学习下！！！不错！
页:
[1]