View difference between Paste ID: DStgW5XK and ZReTtE0a
SHOW: | | - or go back to the newest paste.
1
using System;
2
using System.Collections.Generic;
3
using System.Linq;
4
using System.Text;
5
using System.Threading.Tasks;
6
7
namespace Kruskal
8
{
9
    
10
    class Room
11
    {
12
        private int xPos, yPos;
13
        private int group;
14
15
        private bool isOn;
16
        private bool[] isConnected = new bool[4];
17
18
        public Room(int Y, int X, int nGroup)
19
        {
20
            xPos = X;
21
            yPos = Y;
22
            group = nGroup;
23
24
            isOn = true;
25
            isConnected[0] = false;
26
            isConnected[1] = false;
27
            isConnected[2] = false;
28
            isConnected[3] = false;
29
        }
30
31
        public int getXPos()
32
        {
33
            return xPos;
34
        }
35
36
        public void setXPos(int value)
37
        {
38
            xPos = value;
39
        }
40
41
        public int getYPos()
42
        {
43
            return yPos;
44
        }
45
46
        public void setYPos(int value)
47
        {
48
            yPos = value;
49
        }
50
51
        public int getGroup()
52
        {
53
            return group;
54
        }
55
56
        public void setGroup(int value)
57
        {
58
            group = value;
59
        }
60
61
        public bool getIsOn()
62
        {
63
            return isOn;
64
        }
65
66
        public void setIsOn(bool value)
67
        {
68
            isOn = value;
69
        }
70
71
        public bool getIsConnected(int index)
72
        {
73
            try
74
            {
75
                return isConnected[index];
76
            }
77
            catch
78
            {
79
                Console.Write("Connection Array Out of Range");
80
                return true;
81
            }
82
        }
83
84
        public void setIsConnected(int index, bool value)
85
        {
86
            try
87
            {
88
                isConnected[index] = value;
89
            }
90
            catch
91
            {
92
                Console.SetCursorPosition(0, 20);
93
                Console.Write("Connection Array out of Range");
94
            }
95
        }
96
    }
97
98
    class Program
99
    {
100
        static void Main(string[] args)
101
        {
102
            List<Room> mazeToCheck = new List<Room>();
103
            List<Room> mazeChecked = new List<Room>();
104
105
  
106
107
            int sizeX, sizeY;
108
            sizeY = Convert.ToInt32(Console.ReadLine());
109
            sizeX = Convert.ToInt32(Console.ReadLine());
110
111
            Console.Clear();    
112
113
114
            Room[] maze = new Room[sizeX * sizeY];
115
            HashSet<Room>[] vertexSets = new HashSet<Room>[sizeX * sizeY];
116
117
            /*
118
             *
119
             *Inicialização dos nodes do labirinto
120
             *    e inserção dos nodes em grupos isolados 
121
             * 
122
             */
123
            for (int i = 0; i < sizeY; i++){
124
                for(int j = 0; j < sizeX; j++){
125
                    int curIndex = i * sizeX + j;
126
                    maze[curIndex] = new Room(i, j, curIndex);
127
                    mazeToCheck.Add(maze[curIndex]);
128
                    vertexSets[curIndex] = new HashSet<Room>();
129
                    vertexSets[curIndex].Add(maze[curIndex]);
130
                    
131
                }
132
            }
133
134
            Random random = new Random();
135
            int randNode;
136
137
138
            /*
139
             * Enquanto houver nodes para serem checados
140
             * escolher um node aleatorio na lista de nodes
141
             * descobrir sua coordenada, e procurar nodes vizinhos
142
             */
143
144
            int nodes = 0;
145
            while(mazeToCheck.Count > 0)
146
            {
147
                nodes++;
148
                randNode = random.Next(0, mazeToCheck.Count);
149
                Room currentNode = mazeToCheck[randNode];
150
                Room destNode;
151
                List<int> connectionsToCheck = new List<int>();
152
153
154
                //Condições de checagem
155
                ///Se o node estiver no extremo esquerdo:   nao procurar no X- (West-0)
156
                ///Se o node estiver no extremo direito:    nao procurar no X+ (East-2)
157
                ///se o node estiver no extremo topo:       nao procurar no Y- (North-1)
158
                ///Se o node estiver no extremo baixo:      nao procurar no Y+ (South-3)
159
                                
160
                //Extrema esquerda (west)
161
                if(currentNode.getXPos() > 0)
162
                {
163
                    connectionsToCheck.Add(0);
164
                }
165
                //Extrema direita (east)
166
                if(currentNode.getXPos() < sizeX - 1)
167
                {
168
                    connectionsToCheck.Add(2);
169
                }
170
                //Extremo topo (north)
171
                if(currentNode.getYPos() > 0)
172
                {
173
                    connectionsToCheck.Add(1);
174
                }
175
                //Extremo baixo (south)
176
                if(currentNode.getYPos() < sizeY - 1)
177
                {
178
                    connectionsToCheck.Add(3);
179
                }
180
181
                //Placeholder
182
                
183
                
184
                //Placeholder
185
186
                //Checar o vertice escolhido
187
                //Se o node linkado ao vertice for do mesmo grupo do node atual, descartar vertice e tentar novamente (tentar ate a lista de vertices esvaziar)
188
                //Se a lista de vertices esvaziar e nenhum vertice for escolhido, desconsiderar node (para nao criar loops) e continuar para o proximo
189
190
                //Aqui o node tera uma lista de possiveis conexões
191
                //Deve agora comparar o node da conexão escolhida aleatoriamente para saber se esta no mesmo grupo
192
                bool foundConnection = false;
193
                while (connectionsToCheck.Count > 0 && foundConnection == false)
194
                {
195
                    int randomConnection = connectionsToCheck[random.Next(0, connectionsToCheck.Count)];
196
                    //Console.WriteLine("Current Node: {2} Connection Count: {0} RandomConnection: {1}", connectionsToCheck.Count, randomConnection, nodes);
197
198
                    int destGroup;
199
                    switch (randomConnection)
200
                    {
201
                        //West Check (X - 1)
202
                        case 0:
203
                            //armazena o node ligado ao vertice escolhido
204
                            destNode = maze[currentNode.getYPos() * sizeX + currentNode.getXPos() - 1];
205
206
                            /*
207
                            * se os nodes pertencem ao mesmo grupo
208
                            * remover o vertice atual da checagem, e continuar tentando se houver mais vertices
209
                            *
210
                            * se os nodes forem de grupos diferentes, transferir o node destino ao grupo do node atual
211
                            */
212
213
                            if (CheckRoomsGroup(currentNode, destNode))
214
                            {
215
                                connectionsToCheck.RemoveAt(connectionsToCheck.IndexOf(0));
216
                            }
217
                            else
218
                            {
219
                                //armazena o indice do node destino
220
                                destGroup = maze[currentNode.getYPos() * sizeX + currentNode.getXPos() - 1].getGroup();
221
222
                                //faz a união do conjunto de sets
223
                                vertexSets[currentNode.getGroup()].UnionWith(vertexSets[destGroup]);
224
                                foreach(Room r in vertexSets[destGroup])
225
                                {
226
                                    maze[r.getYPos() * sizeX + r.getXPos()].setGroup(currentNode.getGroup());
227
                                }
228
                                maze[currentNode.getYPos() * sizeX + currentNode.getXPos()].setIsConnected(randomConnection, true);
229
230
                                //indica que uma conexão foi feita
231
                                foundConnection = true;
232
                            }
233
                            break;
234
                        //North Check (Y - 1)
235
                        case 1:
236
237
                            destNode = maze[(currentNode.getYPos() - 1) * sizeX + currentNode.getXPos()];
238
239
                            if (CheckRoomsGroup(currentNode, destNode)){
240
                                connectionsToCheck.RemoveAt(connectionsToCheck.IndexOf(1));
241
                            }else
242
                            {
243
                                destGroup = maze[(currentNode.getYPos() - 1) * sizeX + currentNode.getXPos()].getGroup();
244
245
                                vertexSets[currentNode.getGroup()].UnionWith(vertexSets[destGroup]);
246
                                foreach (Room r in vertexSets[destGroup])
247
                                {
248
                                    maze[r.getYPos() * sizeX + r.getXPos()].setGroup(currentNode.getGroup());
249
                                }
250
251
                                maze[currentNode.getYPos() * sizeX + currentNode.getXPos()].setIsConnected(randomConnection, true);
252
                                foundConnection = true;
253
                            }
254
                            break;
255
                        //East Check (X + 1)
256
                        case 2:
257
258
                            destNode = maze[(currentNode.getYPos() * sizeX + currentNode.getXPos() + 1)];
259
260
                            if (CheckRoomsGroup(currentNode, destNode))
261
                            {
262
                                connectionsToCheck.RemoveAt(connectionsToCheck.IndexOf(2));
263
                            }
264
                            else
265
                            {
266
                                destGroup = maze[(currentNode.getYPos() * sizeX + currentNode.getXPos() + 1)].getGroup();
267
268
                                vertexSets[currentNode.getGroup()].UnionWith(vertexSets[destGroup]);
269
                                foreach (Room r in vertexSets[destGroup])
270
                                {
271
                                    maze[r.getYPos() * sizeX + r.getXPos()].setGroup(currentNode.getGroup());
272
                                }
273
274
                                maze[currentNode.getYPos() * sizeX + currentNode.getXPos()].setIsConnected(randomConnection, true);
275
                                foundConnection = true;
276
                            }
277
                            break;
278
                        //South Check (Y + 1)
279
                        case 3:
280
281
                            destNode = maze[((currentNode.getYPos() + 1) * sizeX + currentNode.getXPos())];
282
283
                            if (CheckRoomsGroup(currentNode, destNode))
284
                            {
285
                                connectionsToCheck.RemoveAt(connectionsToCheck.IndexOf(3));
286
                            }
287
                            else
288
                            {
289
                                destGroup = maze[((currentNode.getYPos() + 1) * sizeX + currentNode.getXPos())].getGroup();
290
291
                                vertexSets[currentNode.getGroup()].UnionWith(vertexSets[destGroup]);
292
                                foreach (Room r in vertexSets[destGroup])
293
                                {
294
                                    maze[r.getYPos() * sizeX + r.getXPos()].setGroup(currentNode.getGroup());
295
                                }
296
                                foundConnection = true;
297
                                maze[currentNode.getYPos() * sizeX + currentNode.getXPos()].setIsConnected(randomConnection, true);
298
                            }
299
                            break;
300
                    }
301
                    PrintMaze(maze, sizeY, sizeX);
302
                    Console.ReadLine();
303
304
                }
305
                mazeChecked.Add(mazeToCheck[randNode]);
306
                mazeToCheck.RemoveAt(randNode);
307
               
308
                connectionsToCheck.Clear();
309
            }
310
           
311
                    //InitMaze(maze, sizeY, sizeX);
312
                    PrintMaze(maze, sizeY, sizeX);
313
            Console.Read();
314
315
        }
316
317
        ///<summary>Check if two rooms are in the same group</summary>
318
        static bool CheckRoomsGroup(Room room1, Room room2)
319
        {
320
            if(room1.getGroup() == room2.getGroup())
321
            {
322
                return true;
323
            }else
324
            {
325
                return false;
326
            }
327
328
        }
329
330
        static void PrintMaze(Room[] maze, int sizeY, int sizeX)
331
        {
332
            for (int i = 0; i < sizeY; i++)
333
            {
334
                for (int j = 0; j < sizeX; j++)
335
                {
336
                    int curIndex = i * sizeX + j;
337
                    Console.SetCursorPosition(maze[curIndex].getXPos() * 2, maze[curIndex].getYPos() * 2);
338
                    if (maze[curIndex].getIsOn())
339
                    {
340
                        Console.Write("{0}",maze[curIndex].getGroup());
341
                    }
342
                    //West Check
343
                    if (maze[curIndex].getIsConnected(0) == true && maze[curIndex].getXPos() * 2 - 1 > 0)
344
                    {
345
                        Console.SetCursorPosition(maze[curIndex].getXPos() * 2 - 1, maze[curIndex].getYPos() * 2 + 0);
346
                        Console.Write("─");
347
                    }
348
349
                    //North Check
350
                    if (maze[curIndex].getIsConnected(1) == true && maze[curIndex].getYPos() * 2 - 1 > 0)
351
                    {
352
                        Console.SetCursorPosition(maze[curIndex].getXPos() * 2 + 0, maze[curIndex].getYPos() * 2 - 1);
353
                        Console.Write("│");
354
                    }
355
356
                    //East Check
357
                    if (maze[curIndex].getIsConnected(2) == true && maze[curIndex].getXPos() * 2 + 1 < sizeX * 2 - 2)
358
                    {
359
                        Console.SetCursorPosition(maze[curIndex].getXPos() * 2 + 1, maze[curIndex].getYPos() * 2 + 0);
360
                        Console.Write("─");
361
                    }
362
363
                    //South Check
364
                    if (maze[curIndex].getIsConnected(3) == true && maze[curIndex].getYPos() * 2 + 1 < sizeY * 2 - 2)
365
                    {
366
                        Console.SetCursorPosition(maze[curIndex].getXPos() * 2 + 0, maze[curIndex].getYPos() * 2 + 1);
367
                        Console.Write("│");
368
                    }
369
                }
370
            }
371
        }
372
    }
373
}