For this last programming project, you will be imp... (3 bookmarks) For this last programming project, you will be implementing several data structures and algorithms that we discussed in class. Since this programming project is relatively larger than the first 3 programming projects you had, you can pair up with one of your classmates and complete this project in 3 weeks. I highly recommend that you start working on this project as soon as possible and not to wait to the last week or days before starting. Additionally, the weight for this last project will be twice the weight of each of the first 3 projects you had. This project asks you to write a program that can: Generate a random two-dimensional square maze whose size is specified by the user; and Read in a maze from a given text file (more about this later). Once the program has generated a random maze or read in a maze from a file, the program would solve the maze by finding a path from the start position to the goal position in the maze. Because of the how the maze is generated (to be discussed next) or specified in the file, there will always be a path from the starting position to the goal position in the maze. The maze structure: The maze is an nn grid of cells (which we also call rooms), where n is a positive integer specified by the user. Each room in the maze can have at most 4 doors, each of which (if open) can lead to the adjacent room to the north, south, east, or west. There is a passage way between two adjacent rooms if and only if both doors connecting the two adjacent rooms are open. There are two special rooms in the maze called the start room and the goal room. The start room is always the upper-left room in the maze and the goal room is always the bottom-right room in the maze. The start room has its door leading to the north always open while the goal room has its door leading to the south always open. Rooms on the boundary of the maze (except the start and goal rooms) have their doors leading out of the maze always close. As an example, the following figure shows a randomly generated 5 5 maze rendered in ASCII characters where each horizontal or vertical line character denotes closed door(s).

Please do not respond unless your code fufills all the requirements.

Please note that I need the output of the code to be what is shown in the example. Meaning that the maze has be made using the charcaters shown in the following image.

Thank You!

Summer 2017 Data Structures Programming Project 4 (Rat-in-a-Maze) For this last programming project, you will be implementing several data structures and algorithms that we discussed in class. Since this programming project is relatively larger than the first 3 programming projects you had, you can pair up with one of your classmates and complete this project in 3 weeks. I highly recommend that you start working on this project as soon as possible and not to wait to the last week or days before starting. Additionally, the weight for this last project will be twice the weight of each of the first 3 projects you had. This project asks you to write a program that can: Generate a random two-dimensional square maze whose size is specified by the user; and Read in a maze from a given text file (more about this later). Once the program has generated a random maze or read in a maze from a file, the program would solve the maze by finding a path from the start position to the goal position in the maze. Because of the how the maze is generated (to be discussed next) or specified in the file, there will always be a path from the starting position to the goal position in the maze. The maze structure: The maze is an nn grid of cells (which we also call rooms), where n is a positive integer specified by the user. Each room in the maze can have at most 4 doors, each of which (if open) can lead to the adjacent room to the north, south, east, or west. There is a passage way between two adjacent rooms if and only if both doors connecting the two adjacent rooms are open. There are two special rooms in the maze called the start room and the goal room. The start room is always the upper-left room in the maze and the goal room is always the bottom-right room in the maze. The start room has its door leading to the north always open while the goal room has its door leading to the south always open. Rooms on the boundary of the maze (except the start and goal rooms) have their doors leading out of the maze always close. As an example, the following figure shows a randomly generated 5 5 maze rendered in ASCII characters where each horizontal or vertical line character denotes closed door(s). Maze generation: To randomly generate an nxn maze, we use the algorithm below. The algorithm assumes that the rooms are uniquely numbered from left to right, top to bottom. The numbering of rooms starts from 0 and ends with N-1, where N is the total number of rooms in the maze (i.e., N = n) For the example maze given above, the start room is numbered 0 while the goal room is numbered 24