hello friend !
if any person make this assignment then plz solve this assignment and send me my email adress "
[email protected] "
Assignment is :
In this problem, you will use the disjoint set data structure to construct a random maze -- drawn on an N-by-N grid of cells -- so that there is exactly one path from the top-left cell to the bottom-right cell.
Building the maze. Details on using the disjoint data structure to build a random maze are given in the text. We review the procedure briefly here. Consider an N-by-N grid of cells, initially with each cell surrounded on all sides by "walls". For example, the picture for N=4 would look like:
+--+--+--+--+
|S | | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | | F|
+--+--+--+--+
S and F mark the start and finish cells. We consider each of the cells -- numbered 0, 1, ... , N2-1 -- to initially be in separate equivalence classes. We build the maze by randomly selecting an interior wall and removing it only if the two cells adjacent to the wall belong to different equivalence classes. When we remove the wall, we perform a union on the equivalence classes represented by the adjacent cells. The disjoint set data structure keeps track of equivalence classes of cells that are reachable from each other through paths in the maze. Note that we also need to keep track of which walls are left in the maze so that we will be able to draw it later; thus, the disjoint set data structure alone will not suffice to build the tree. We keep randomly removing edges until every cell is the same equivalence class.
read the value of N, the size of maze
Put every cell in its own set
Iterate
Choose an interior wall at random
Perform union on the adjacent cells if they are not already
in the same set
until everything is in one set
print the maze
Suggestion: think about how many unions you need to perform. An example of a possible final maze in the N=4 case would be
+--+--+--+--+
|S | |
+--+ + + +
| | |
+ + +--+ +
| | | | |
+ +--+ + +
| | F|
+--+--+--+--+
General comments and guidelines. This problem, conceptually, is a straightforward application of the disjoint sets and graph data structures. However, to avoid bugs and have clean code for your solution, the most important part of the problem is to design the structure of your program carefully and use good object-oriented coding practices. Details of the representation(s) of the maze should be encapsulated inside classes. Figuring out, for example, whether 2 cells are adjacent in the grid should be done by a call to a short method -- the main flow of your algorithm should not be cluttered with handling such details. Your code should be clean, elegant and well-structured.
Random number generation. The C++ runtime library includes routines for generating random numbers. The included C++ file testrand.cpp demonstrates the use of these routines.
_________________________________________________
helping file in assignment is
// Example program that shows the use of the random number generation
// using the runtime library routine 'rand()'
//
#include
#include
void main(int argc, char *argv[])
{
int genRandom(int, int );
int i;
// Seed the random number generator. The signature of 'srand' is
// srand(unsigned int seed)
// A different seed will produce different set of random numbers.
//
srand(6);
// generate 15 random numbers between 0 and 3
for(i=0; i < 15; i++ ) {
printf("j= %d\n", genRandom(0,3) );
}
system("PAUSE");
}
// return random number between x and y
int genRandom(int x, int y )
{
return x+(int) ((y*1.0)*rand()/(RAND_MAX+1.0));
}
_____________
please any person solve this assignment