|
现在介绍第二种算法，使用并查集 合并生成。
简单介绍一下算法思想：首先把地图关键点的连结（墙），编号1-x*y*2，然后random shuffle
然后按照打乱后的次序，打通一些墙，用并查集检查是否要打通的两边是已经连通的就行了，
生成的例子如下：
█████████████████████
█ █ █
█████████ █ █ █ █████
█ █ █ █ █ █ █
█ █ █ ███ █████ █ █ █
█ █ █ █ █ █ █ █
█ █ ███ ███ ███ ███ █
█ █ █ █
█████ ███ █ █ ███ ███
█ █ █ █ █ █
█████ ███ ███████ █ █
█ █ █ █
█ ███ █ ███ █ █ █████
█ █ █ █ █ █ █
███ ███████ █ █ ███ █
█ █ █ █ █
█████████████████████
?
这种算法生成的特点是，分支数非常的多，较多短小分支，难度往往较DFS生成的简单
但效率非常高，生成1000*1000的迷宫，只要1秒（DFS生成的常数上要大一些）
但需要一个辅助的并查集数据结构，空间消耗大。
代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SWAP(a,b,c) {c t=a;a=b;b=t;}
int uf[9000000],Map[3000][3000]; //并查集表，迷宫地图
struct PT{int x; int y;}que[5000000]; //生成序列
int x=10,y=8,xy=0; //x,y指定要生成的大小
int findP(int& n)
{
????int a=++n;
????while (uf[a]) a=uf[a];
????if (a!=n) uf[n] = a;
????return n=a;
}
int Ins(PT xy)
{
????int a=(xy.y-1)/2*x+(xy.x-1)/2,b=(xy.y&1)?a+1:a+x;
????if (findP(a)!=findP(b)) {uf[b] = a; return 1;}
????return 0;
}
int main()
{
????int n=0,_y,_x,o;
????srand(time(NULL)); Map[1][0]=Map[y*2-1][x*2]=1;
????for (_y=1; o=_y!=y,_y<=y; ++_y)
????????for (_x=1; _x<=x; ++_x)
????????{
????????????if (_x<x)que[n].y = _y*2-1,que[n].x = _x*2,++n;
????????????if (o)que[n].y = _y*2,que[n].x = _x*2-1,++n;
????????}
????for (xy=n,n=0; n<xy; ++n) {int z=rand()%xy; SWAP(que[n],que[z],PT);}
????for (n=0; n<xy; ++n)
????{
????????if (!Ins(que[n])) continue;
????????Map[que[n].y][que[n].x] = 1;
????????if (que[n].y&1) Map[que[n].y][que[n].x-1] = Map[que[n].y][que[n].x+1] = 1;
????????else Map[que[n].y-1][que[n].x] = Map[que[n].y+1][que[n].x] = 1;
????}
????for (_y=0; _y<=y*2; ++_y)
????{
????????for (_x=0; _x<=x*2; ++_x)
????????????????if (Map[_y][_x]) fputs(" ",stdout); else fputs("█",stdout);
????????putchar(10);
????}
????return 0;
} （编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
