Reference no: EM132081369
You need question number 6 answered, but You do know that question #6 referenced #5 so that is why You supplied you with question #5.
5. Perfect maze. Generate a perfect maze like this one
14-by-14 perfect maze 22-by-22 perfect maze
Write a program Maze.java that takes a command line parameter N, and generates a random N-by-N perfect maze.
A maze is perfect if it has exactly one path between every pair of points in the maze, i.e., no inaccessible locations, no cycles, and no open spaces. Here's a nice algorithm to generate such mazes.
Consider an N-by-N grid of cells, each of which initially has a wall between it and its four neighboring cells.
For each cell (x, y), maintain a variable north[x][y] that is true if there is wall separating (x, y) and (x, y + 1). We have analogous variables east[x][y], south[x][y], and west[x][y] for the corresponding walls.
Note that if there is a wall to the north of (x, y) then north[x][y] = south[x][y+1] = true. Construct the maze by knocking down some of the walls as follows:
a. Start at the lower level cell (1, 1).
b. Find a neighbor at random that you haven't yet been to.
c. If you find one, move there, knocking down the wall. If you don't find one, go back to the previous cell.
d. Repeat steps ii. and iii. until you've been to every cell in the grid.
Hint: maintain an (N+2)-by-(N+2) grid of cells to avoid tedious special cases.
6. Getting out of the maze. Given an N-by-N maze (like the one created in the previous exercise), write a program to find a path from the start cell (1, 1) to the finish cell (N, N), if it exists. To find a solution to the maze, run the following algorithm, starting from (1, 1) and stopping if we reach cell (N, N).
explore(x, y)
-------------
- Mark the current cell (x, y) as "visited."
- If no wall to north and unvisited, then explore(x, y+1).
- If no wall to east and unvisited, then explore(x+1, y).
- If no wall to south and unvisited, then explore(x, y-1).
- If no wall to west and unvisited, then explore(x-1, y).