In this homework, first, you will implement a program which will generate a random maze of size MxN, where M represents the number of rows, and N represents the number of columns. Then, you will also need to implement a function which will find the path between designated entry and exit points in a given maze.

To do this homework, you are required to implement a Stack using a LinkedList data structure, i.e., you can not use vectors in the stack implementation. The stack class MUST be a template-based class. You may want to store basic data types, structs or classes in this stack.

The Maze

The mazes are presented as MxN (M rows and N columns) 2D vectors as given below. The left bottom of the mazes are considered to be the (0,0) coordinate. There are 2 important rules for a given 2D vector to be a maze:

• Every cell must be reachable from any other cell.
• The reachability of cells from one to another must be unique, i.e., there must be only one path from a cell to another.

Some example mazes of size 55 and 36 can be found below. Note there are no entry or exit points yet.

We also share some invalid maze examples below. In both mazes, for some cell pairs (c1 ,c2), there are more than one path to reach from c1 to c2.

Program Flow

There are 2 phases of this homework;

1. The maze generation.
2. Finding a path for given entry and exit points.

In both phases, you MUST use the stacks to solve the problem!

The maze generation

In this phase, you need to generate K random MXN mazes using stacks for given M, N and K values. The general idea to generate a maze is to knock down walls between 2 cells, iteratively, until no unvisited cell remains. Hence, you need to knock down exactly MxN-1 walls. In each step, the maze rules (given above in the maze definition) must apply all the time.

The basic steps are:

1. Start with an initially empty stack.
2. Push (0,0) cell to your stack.
3. Use the top element (currentCell) in the stack to choose the next cell to be added to your maze.
4. Choose a random wall of the currentCell to add a new unvisited cell to the maze.
5. Knock down the wall and add the new cell to the stack.
6. If no wall exists to knock down for the currentCell, backtrack using the stack until you find a cell which has an unvisited neighbour cell.
7. Continue steps 3-6 until no cell remains unvisited.

Path discovery in a maze

Finding a path is almost the same as the maze generation process. First, the program will ask the user which maze should be chosen among the ones generated in the first phase. Then, the program;

1. Start with an initially empty stack.
2. Push the entry cell to your stack (will be entered by the user).
3. Use the top element in the stack to choose the next cell to visit.
4. If you cannot find any cell to go, backtrack using the stack until you find an unvisited cell to go.
5. Continue steps 3-4 until you reach the exit point. Note that the path generated in this phase MUST be unique! You can assume that:

• All the inputs entered by the user are valid, you do not need to validate them.
• The entry and exit points of the mazes are on the edges or corners of the mazes.

Input and Output

In the first phase, your program will ask the user to enter 3 inputs, namely, K, M, and N. You can assume that M and N are greater than 1, and K is a positive integer. However, your program should be able to generate huge mazes, too.

You will write your mazes into a file named as maze_mazeID.txt, where mazeID will go from 1 to K such as maze_1.txt and maze_4.txt. Your output format must be exactly the same format as we give below. In the first line, sizes of the maze, M and N, must be given. In the following lines, for each cell, the x and y coordinates of the cell, as well as the walls of the cell, must be given. If there is a wall on the left (l), right (r), up (u), or down (d), assign 1 to the wall, if not, assign 0. For example, in the maze_1.txt below, at (0,0) cell, there are walls on the left, right and down side, but not on the up side. maze_1.txt

5 4

x=0 y=0 l=1 r=1 u=0 d=1

x=1 y=0 l=1 r=0 u=1 d=1 x=2 y=0 l=0 r=0 u=1 d=1

In the second phase (after the mazes are generated), your program will ask the user to enter 5 more inputs; mazeID, entryX, entryY, exitX, and exitY. Maze ID will be a number between 1 and K, i.e., 1 <= mazeID <= K, indicating the specific mazes that are generated in the first phase to be traveled. For example, if mazeID = 3, then, the program needs to find a path for the third maze. entryX and entryY are the coordinates for entry point, and exitX and exitY are the coordinates for the exit point. Note that, y coordinates becomes the row of the maze and x coordinates becomes the column of the maze. For instance, the point (2,4) refers to the 4th row and 2nd column of the maze.

The output will be written to a file named as maze_mazeID_path_entryX_entryY_exitX_exitY.txt. For instance, for the maze with mazeID = 2, entry = (0,0) and exit = (3,4), the file name will be maze_2_path_0_0_3_4.txt.

In the output file, the coordinates of the cells to get the exit point from entry point must be written line by line. See example output file below: maze_2_path_0_0_3_4.txt

0 0

3 4

Debugging your code

We will provide a mazeDrawer program (mazeDrawer.exe for windows, mazeDrawer.linux for Linux and mazeDrawer.mac for macOS machines) for you to draw any given maze. To draw the maze for a given input file described above (maze_1txt), you must apply the following rules:

On windows machine:

1. Put the mazeDrawer.exe and the input files into the same folder.
2. Click on mazeDrawer.exe.
3. Follow the instructions as needed.

On macOS or Linux machine:

1. Put the mazeDrawer (mazeDrawer.mac for macOS and mazeDrawer.linux for Linux) program and the input files into the same folder.
2. For macOS;
   1. Open a Terminal.app
   2. Copy the folder with Command+C (this will copy the path to reach the folder)

• In terminal, type cd

1. Use Command+V to paste the folder path and click enter Example usage (assuming mazeDrawer.mac is in the following path):

cd /Users/oguzozsaygin/Homework1

For Linux;

1. Go to the folder.
2. Right click anywhere in the folder. iii. Click open a terminal .
3. Execute the following command on the terminal by typing:
4. For macOS;

./mazeDrawer.mac

1. For Linux;

./mazeDrawer.linux 4. Follow the instructions as needed.

If you face any issues running the mazeDrawer program, please go to an office hour or ask your TA to explain it in the recitation.

You will be given the file maze_example.txt to draw the maze below as an example. Use it as a way to understand how to use the program. This program is for you to better visualize your maze, though you are not obligated, we highly recommended you to use it for debugging your code.

Sample Run

Enter the number of mazes: 5

Enter the number of rows and columns (M and N): 20 32

All mazes are generated.

Enter a maze ID between 1 to 5 inclusive to find a path: 1

Enter x and y coordinates of the entry points (x,y) or (column,row): 0 0

Enter x and y coordinates of the exit points (x,y) or (column,row):