|
之前所有的迷宫生成算法，空间都是O(mn)，时间同样是O(mn)，时间上已经不可能更优化，
于是，我就从空间优化上着手，研究一个仅用O(n)空间的生成算法。
我初步的想法是，每次生成一行，生成后立即输出，而其连通性的信息用并查集保存。
然而这时却遇到阻力：不可能简单保存连通性信息就能完成。
因为通过上一行的信息去生成下一行的时候，仅靠连通性信息你无法知道你能不能结束当前路径上的连结，
也就是说你不能判断你能不能生成一个死胡同。
?
后来想了一下，改进了一下并查集，让它的父结点多保存一个信息：当前行与本结点连通的格子数
看这个例子：
━┳━━┳━━┳━━━━┳━━┳━━┳┓
┣┓┗━┃┃━━┛━━━┓┃┃┃┗┓┃┃┃
┃┗┳━┫┗━━┓┏━━┫┏┛┣━┃┃┃┃
?1 1??1 1 2 2 2 2 3?6?6?6 3 3 3 3 3 4 4 5
相同数字的表示它们连通（连向同一个父结点），比如3那个，当前行与本结点连通的格子数=6
也就是3出现的次数。
在生成下一行的时候，每生成一个格子，就得同时更新连通格子数的值，以保证不会生成环路和死路
参考源代码：
#include <iostream>
#include <ctime>
using namespace std;
#define next(n,s) ((n)=(n)%((s)-1)+1)
int fset_size;
struct data
{
????int parent;
????int level;
????int sum;
}*fset;
int fset_pt = 1,fdeep;
int try_alloc(int level)
{
????if (fset[fset_pt].level < level)
????{
????????return fset_pt;
????}
????int lpt = fset_pt;
????for (next(fset_pt,fset_size); fset_pt!=lpt; next(fset_pt,fset_size))
????{
????????if (fset[fset_pt].level < level)
????????{
????????????return fset_pt;
????????}
????}
????return 0;
}
int reg_fset(int level)
{
????int lpt = fset_pt;
????fset[fset_pt].level = level;
????fset[fset_pt].parent = 0;
????fset[fset_pt].sum = 1;
????next(fset_pt,fset_size);
????return lpt;
}
int get_parent(int id)
{
????int d = id;
????for (fdeep=0; fset[id].parent>0; ++fdeep)
????????id = fset[id].parent;
????if (d != id) fset[d].parent = id;
????return id;
}
void insert(int a,int b)
{
????int pa = get_parent(a),da = fdeep;
????int pb = get_parent(b),db = fdeep;
????if (pa==pb)
????{
????}
????else if (da<=db)
????{
????????fset[pa].parent = pb;
????????fset[pb].level = max(fset[pa].level,fset[pb].level);
????????fset[pb].sum += fset[pa].sum-1;
????}
????else
????{
????????fset[pb].parent = pa;
????????fset[pa].level = max(fset[pa].level,fset[pb].level);
????????fset[pa].sum += fset[pb].sum-1;
????}
}
int is_connect(int a,int b)
{
????if (a==b || get_parent(a)==get_parent(b))
????????return 1;
????return 0;
}
struct tile
{
????int wall;
????int id;
};
char cw[][4]={" ","━","┃","┛","┗","┻","┓","┫","┏","┳","┣","╋"};
int Gen(int w,int h)
{
????int x,y,lx,ly,p;
????tile* maze = (tile*)malloc(sizeof(tile)*(w+2));
????fset = (data*)malloc(sizeof(data)*(w*2));
????fset_size = w;
????memset(fset,sizeof(data)*(w*2));
????for (x=0; x<=w+1; ++x) maze[x].wall = 7,maze[x].id=0;
????maze[0].wall = 15; maze[w+1].wall = 15;
????for (y=1; y<=h+1; ++y,maze[0].wall = 11,maze[w+1].wall = 14)
????{
????????lx = 0; ly = 1; x = 0;
????????fset[0].sum = 0;
????????p = 15;
????????if (lx) p &= ~8;
????????if (ly) p &= ~1;
????????if (maze[x+1].wall&8) p &= ~4;
????????if (is_connect(maze[x].id,maze[x+1].id)) p &= ~2;
????????if (y>h) p &= ~8;
????????printf(cw[p]);
????????p &= 4;
????????printf(cw[p]);
????????for (x=1; x<=w; ++x)
????????{
????????????int r,_r = 4;
????????????ly = (maze[x].wall&8);
????????????int id,dsum = 0;
????????????if (lx && ly)
????????????{
????????????????insert(maze[x-1].id,maze[x].id);
????????????}
????????????else if (lx==0 && ly==0)
????????????{
????????????????maze[x].id = try_alloc(y);
????????????????if (maze[x].id==0)
????????????????{
????????????????????fset_size += w;
????????????????????maze[x].id = try_alloc(y);
????????????????????fset_size -= w;
????????????????}
????????????????reg_fset(y+1);
????????????}
????????????else if (lx)
????????????{
????????????????maze[x].id = maze[x-1].id;
????????????}
????????????id = get_parent(maze[x].id);
????????????if ((maze[x+1].wall&8) && is_connect(maze[x].id,maze[x+1].id)) _r = 2;
????????????if (y==h && x==w)
????????????{
????????????????r = 0;
????????????}
????????????else do
????????????{
????????????????r = rand() % _r;
????????????????if ((r&2)==0 && try_alloc(y)==0) r |= 2;
????????????????if (y>h)
????????????????{
????????????????????r = 2;
????????????????}
????????????????else if (x==w) r &= ~2;
????????????????if (y==h) r &= ~1;
????????????????dsum = 0;
????????????????if ((r & 1) == 0 ) dsum -= 1;
????????????????if (r & 2) dsum += 1;
????????????}
????????????while (y<=h && ((r==0 && (lx==0 && ly==0) || fset[id].sum+dsum<=0 )) );
????????????maze[x].wall = 0;
????????????if (ly) maze[x].wall |= 2;
????????????if (lx)
????????????{
????????????????maze[x].wall |= 1;
????????????}
????????????lx = (r&2);
????????????if (lx) maze[x].wall |= 4;
????????????if (r&1) maze[x].wall |= 8;
????????????p = 15;
????????????if (maze[x].wall&4) fset[id].sum += 1;
????????????if ((maze[x].wall&8)==0) fset[id].sum -= 1,fset[0].sum += 1;
????????????fset[id].level = y+1;
????????????if (maze[x].wall&4) p &= ~8;
????????????if (maze[x].wall&2) p &= ~1;
????????????if (maze[x+1].wall&8) p &= ~4;
????????????if (maze[x+1].wall&1) p &= ~2;
????????????printf(cw[p]);
????????????p &= 4;
????????????printf(cw[p]);
????????}
????????puts("");
????????if (y<h)
????????{
????????????for (x=0; x<=w; ++x)
????????????{
????????????????if (maze[x].wall&4) printf(cw[0]); else printf(cw[10]);
????????????????int id = get_parent(maze[x].id);
????????????????maze[x].id = id;
????????????????printf(cw[0]);
????????????}
????????????puts("");
????????}
????????else if (y==h)
????????{
????????????for (x=0; x<=w; ++x)
????????????{
????????????????if ((maze[x].wall&4) || x==w) printf(cw[0]); else printf(cw[10]);
????????????????int id = get_parent(maze[x].id);
????????????????maze[x].id = id;
????????????????printf(cw[0]);
????????????}
????????????puts("");
????????}
????}
????free(maze);
????free(fset);
????return 0;
}
int main()
{
????srand((unsigned)time(NULL));
????Gen(15,10);
????return 0;
} （编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
