Answer Happy

Maze(Disjoint Set) C PROGRAM:
PLEASE PROVIDE COMMENTS WITH YOUR CODE!
USE THE SKELETON CODE WITH THE ANSWER!
DISJOINT SET SKELETON CODE:
Input & Output Example :
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
Implement the function that creates Random Maze by
receiving the [input].txt
file as input as below, and the output results of generated Maze
are stored in
the [output].txt file.
-INPUT : Width, Height size of the
Maze(Matrix). (maze is a square matrix, natural number less or
equal to 100)
- OUTPUT : Print out the shape of the generated
Maze.
* STRUCTURE AND FUNCTION FORMAT :
- Struct format above should be used for implementation
- Functions should be implemented in appropriate format as
above.
- Since the edges should be eliminated randomly, output results
after different
execution with the same input value should be different every
time.
- Only one path from the start to end should exist without any
cycle.
Printing Maze:
- space for the Cell is “three space”,
- “---”(three minus operator (not the underbar “_”)) for Horizontal
Edge,
- “three space” when Horizontal edge does not exist,
- “|”(bitwise “or” operator) for Vertical Edge,
- "one space" when Vertical edge does not exist,
- “+” for the rest.
Structure typedef struct _DisjointSet { int size_maze; int *ptr_arr; }DisjointSets; Variable sets means the number between the walls. maze_print means the wall 1:yes, 0:no Function void init (DisjointSets *sets, DisjointSets *maze_print, int num); void Union (DisjointSets *sets, int i, int j); int find (DisjointSets *sets, int i); void createMaze (DisjointSets *sets, DisjointSets *maze_print, int num); void printMaze (DisjointSets *sets, int num); void freeMaze (DisjointSets *sets, DisjointSets *maze_print); Start 1 2 3 5 6 7 89 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 End
#include<stdio.h> 2 #include<stdlib.h> 3 #include<time.h> 4 5 FILE *fin; 6 FILE *fout; 7 8 typedef struct _DisjointSet { 9 int size_maze; 10 int *ptr_arr; 11 }DisjointSets; 12 13 void init(DisjointSets *sets, DisjointSets *maze_print, int num); 14 void Union (DisjointSets *sets, int i, int j); 15 int find (DisjointSets sets, int i); 16 void createMaze (DisjointSets *sets, DisjointSets *maze_print, int num); 17 void printMaze (DisjointSets *sets, int num); 18 void freeMaze (DisjointSets *sets, DisjointSets *maze_print); 19 20 int main(int argc, char* agrv[]) { 21 srand((unsigned int) time(NULL)); 22 23 int num, i; 24 fin = fopen(agrv[1], "r"); 25 fout= fopen(agrv[2], "w"); 26 27 DisjointSets *sets, maze_print; 28 fscanf(fin, "%d", &num); 29 30 sets = (DisjointSets*) malloc(sizeof (DisjointSets)); 31 maze_print = (DisjointSets*) malloc(sizeof (DisjointSets)); 32 33 init(sets, maze_print, num); 34 createMaze (sets, maze_print, num); 35 printMaze (maze_print, num); 36 37 freeMaze (sets, maze_print); 38 39 fclose(fin); 40 fclose(fout); 41 42 return 0; 43 } 45 void init (DisjointSets *sets, DisjointSets *maze_print, int num) { int i; 46 47 48 sets->size_maze = num * num; 49 sets->ptr_arr = (int*) malloc(sizeof(int) * (sets->size_maze + 1)); 50 for (i = 1; i <= sets->size_maze; i++) sets->ptr_arr = i; 51 52 maze_print->size_maze = num * num * 2; 53 maze_print->ptr_arr = (int*)malloc(sizeof(int) * (maze_print->size_maze + 1)); 54 for (i = 1; i <= maze_print->size_maze; i++) maze_print->ptr_arr = 1; 55 //maze_print->ptr_arr[(x-1)*2+1 ~ x*2] : two directions (right, down) walls of the number x 56 57 //start and end position have not to have the wall maze_print->ptr_arr[maze_print->size_maze - 1] = 0; 58 59 }
4 10 --+ +---+ +===+ + +---+ + +---+ ---+---+ --+---+ + ---+--- I --+---+ --+ +---+---+ +---+ + + +---+ --+ --+---+ + + | + + + --+ cat input.txt cat output.txt cat input.txt cat output.txt
4 8 input1.txt A I I I 8 output1.txt A
void init (DisjointSets *sets, DisjointSets *maze_print, int num); void Union (DisjointSets *sets, int i, int j); typedef struct _DisjointSet { int find (DisjointSets *sets, int i); int size_maze; int *ptr_arr; }DisjointSets; void createMaze (DisjointSets *sets, DisjointSets *maze_print, int num); void printMaze (DisjointSets *sets, int num); void freeMaze (DisjointSets *sets, DisjointSets *maze_print);