不相交集类应用：迷宫生成

  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 }