之前所有的迷宫生成算法，空间都是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, 0, 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;
}