[C++] 实现迷宫生成算法 采用了并查集数据结构

Knuth学徒

随机生成一个迷宫，一般这种问题要用并查集的，但是具体算法我没有上网查找过，所以自己想了一个，但是我的想法还不成熟，存在很多缺陷，望大牛们指正。
算法的思想是：
while( 入口和出口 不通)
{
....随机找个点 -> (x,y)
....随机找个方向->上/下/左/右 -> dx,dy = {0,1,-1}
....如果(x,y)和( x + dx , y + dy)有一个是墙
.........把墙去掉
.........联通(x,y) 和 (x+dx,y+dy)
}

如果 RP是负无穷的话，可能要搜很长时间。。。。

1. 
   
2. /*
   
3. *   Auther:Knuth学徒
   
4. *   Lang:C++
   
5. *   Date:2011-2-12
   
6. */
   
7. 
   
8. #include<cstdio>
   
9. #include<cstring>
   
10. #include<cstdlib>
    
11. #include<ctime>
    
12. #include<iOStream>
    
13. using namespace std;
    
14. 
    
15. const int M = 5;
    
16. const int N = 5;
    
17. const int direction[4][2] = {(0,-1),(0,1),(-1,0),(1,0)};
    
18. 
    
19. int father[M*N + 1];   //并查集的父节点记录数组
    
20. int map[N][M];         //地图数组
    
21. 
    
22. /////////////////////////////////////////////////
    
23. //     函数名：hash
    
24. //     参数：横坐标和纵坐标以及棋盘的列大小
    
25. //     前提：None
    
26. //     返回：坐标的散列值
    
27. /////////////////////////////////////////////////
    
28. int hash(int x,int y, int col)
    
29. {
    
30.         return ( x * col + y );
    
31. }
    
32. 
    
33. /////////////////////////////////////////////////
    
34. //     函数名：id
    
35. //     参数：点的散列值，存在a和b中
    
36. //     前提：None
    
37. //     返回：引用传值回去
    
38. /////////////////////////////////////////////////
    
39. void id(int val, int &a,int &b)
    
40. {
    
41.         a = val/M;
    
42.         b = val%M;
    
43. }
    
44. 
    
45. /////////////////////////////////////////////////
    
46. //     函数名：Make
    
47. //     参数：None
    
48. //     前提：None
    
49. //     返回：None
    
50. //     描述：并查集的初始化过程
    
51. /////////////////////////////////////////////////
    
52. void Make()
    
53. {
    
54.         for(int i=0;i<N;++i)
    
55.                 for(int j = 0;j<M;++j)
    
56.                 {
    
57.                         father[hash(i,j,M)] = hash(i,j,M);
    
58.                 //        printf("f[%d] = %d ",hash(i,j,M),father[hash(i,j,M)]);
    
59.                 }
    
60. }
    
61. 
    
62. /////////////////////////////////////////////////
    
63. //     函数名：FindSet
    
64. //     参数：节点X表示某个点的散列值
    
65. //     前提：None
    
66. //     返回：节点x的祖先
    
67. //     描述：递归时采用了路径压缩
    
68. /////////////////////////////////////////////////
    
69. int FindSet(int x)
    
70. {
    
71.         if( x != father[x])
    
72.         {
    
73.                 father[x] = FindSet(x);
    
74.         }
    
75.         return father[x];
    
76. }
    
77. 
    
78. /////////////////////////////////////////////////
    
79. //     函数名：Union
    
80. //     参数：两个散列值
    
81. //     前提：None
    
82. //     返回：None
    
83. //     描述：合并两个集合
    
84. /////////////////////////////////////////////////
    
85. void Union(int a,int b)
    
86. {
    
87.         father[a] = b;
    
88. }
    
89. 
    
90. int main()
    
91. {
    
92.         Make();
    
93.         int sx,sy,ex,ey;
    
94.         srand((unsigned)time(0));
    
95.         int a = rand() % M*N; //入口
    
96.         int b = rand() % M*N;  //出口
    
97.         id(a,sx,sy);
    
98.         id(b,ex,ey);
    
99.         map[sx][sy] = map[ex][ey] = 0;
    
100. //        cout<<"a = "<<a<<endl;
     
101. //        cout<<"b = "<<b<<endl;
     
102.   //  cout<<"f[a]="<<father[a]<<endl;
     
103.     //cout<<"f  b="<<father[b]<<endl;
     
104.         while(FindSet(a) != FindSet(b))
     
105.         //如果入口和出口不联通
     
106.         {
     
107.                 int tmp = rand() % M*N;
     
108.                 //随机选一点
     
109. 
     
110.                 int dire = rand()%4;
     
111.                 int tx,ty,ttx,tty;
     
112.                 id(tmp,tx,ty);
     
113.         //        printf("%d %d",tx,ty);
     
114.                 ttx = tx + direction[dire][0];
     
115.                 tty = ty + direction[dire][1];
     
116. 
     
117.                 if(map[tx][ty] || map[ttx][tty])
     
118.                 {
     
119.                         map[tx][ty] = (map[tx][ty] == 1 ? 0:0);
     
120.                         map[ttx][tty] = (map[ttx][tty] == 1 ? 0:0);
     
121.                         Union(hash(tx,ty,M),hash(ttx,tty,M));
     
122.                 }
     
123.         }
     
124.    // cout<<"OK2"<<endl;
     
125.         for(int m = 0;m<N;++m)
     
126.         {
     
127.                 for(int n =0;n<M;++n)
     
128.                 {
     
129.                         printf("%d",map[m][n]);
     
130.                 }
     
131.                 printf("\n");
     
132.         }
     
133.         return 0;
     
134. }

复制代码

hu251405204

好东西,收藏了

独尚尚

看着 好复杂呀

287965881

学习下！！！不错！