1 #include <iostream>
2 #include <vector>
3 #include <cstdlib>
4 #include <ctime>
5
6 #define N 100
7
8 using namespace std;
9
10 int wall_row[N+1][N];
11 int wall_col[N][N+1];
12
13 class DisjSets
14 {
15 public:
16 explicit DisjSets(int numElements);
17
18 int find(int x) const;
19 void unionSets(int node1, int node2);
20 bool connected(int node1, int node2) const
21 {
22 return find(node1) == find(node2);
23 }
24
25 private:
26 vector<int> s;
27 };
28
29 DisjSets::DisjSets(int numElements):s(numElements)
30 {
31 for (int i = 0; i < s.size(); i++)
32 s[i] = -1;
33 }
34
35 int DisjSets::find(int x) const
36 {
37 if (s[x] < 0)
38 return x;
39 else
40 return find(s[x]);
41 }
42
43 void DisjSets::unionSets(int node1, int node2)
44 {
45 int root1 = find(node1);
46 int root2= find(node2);
47
48 if (root1==root2)
49 return;
50
51 if (s[root2] < s[root1])
52 s[root1] = root2;
53 else
54 {
55 if(s[root1] == s[root2])
56 s[root1]--;
57 s[root2] = root1;
58 }
59 }
60
61 void fill(int value)
62 {
63 int i,j;
64 for(i=0; i<N+1; i++)
65 for(j=0; j<N; j++)
66 wall_row[i][j] = value;
67 for(i=0; i<N; i++)
68 for(j=0; j<N+1; j++)
69 wall_col[i][j] = value;
70 }
71
72 void print()
73 {
74 int i, j;
75 for (i=0; i<N+1; i++)
76 {
77 for (j=0; j<N+1; j++)
78 {
79 if (i > 0)
80 {
81 if(wall_col[i-1][j])
82 cout<<"|";
83 else
84 cout<<" ";
85 }
86 if (j<N)
87 {
88 if (i>0)
89 {
90 if (wall_row[i][j])
91 cout<<"_";
92 else
93 cout<<" ";
94 }
95 else
96 {
97 if(wall_row[i][j])
98 cout<<" _";
99 else
100 cout<<" ";
101 }
102 }
103 }
104 cout<<endl;
105 }
106 }
107
108 void map_rand(int x, int &type, int &a, int &b)
109 {
110 type = 0;
111 if(x >= N*(N-1))
112 type = 1;
113 if(type == 0)
114 {
115 a = x / (N - 1);
116 b = x % (N - 1) + 1;
117 }
118 else
119 {
120 x -= N*(N-1);
121 a = x / N + 1;
122 b = x % N;
123 }
124 }
125
126 void map_pos(int type, int a, int b, int &node1, int &node2)
127 {
128 if(type == 0)
129 {
130 node1 = a * N + b - 1;
131 node2 = a * N + b;
132 } else
133 {
134 node1 = (a - 1) * N + b;
135 node2 = (a - 1) * N + b + N;
136 }
137 }
138
139 int randselect(void)
140 {
141 int range = N*(N-1)*2;
142 return rand() % range;
143 }
144
145 int main()
146 {
147 fill(1); //赋值全部为1
148 srand(time(0));
149 wall_row[0][0] = 0;
150 wall_col[0][0] = 0;
151 wall_row[N][N-1] = 0;
152 wall_col[N-1][N] = 0;//定义出口入口
153
154 int amount = N * N;
155
156 DisjSets s(amount);
157
158 while(!s.connected(0, amount-1)) //是否两个节点相连(相同)
159 {
160 int type, a, b;
161 do
162 {
163 int wall = randselect();
164 map_rand(wall, type, a, b);
165 }
166 while ((type == 0 && wall_col[a][b] == 0) ||(type == 1 && wall_row[a][b] == 0))
167 ;
168 int node1, node2;
169 map_pos(type, a, b, node1, node2);
170 if(!s.connected(node1, node2))
171 {
172 if(type == 0)
173 wall_col[a][b] = 0;
174 else
175 wall_row[a][b] = 0;
176 s.unionSets(node1, node2);
177 }
178 }
179 print();
180 return 0;
181 }
生成结果“