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 | } |