This assignment asks you to write a program that will find a path through a maze. Your implementation should utilize what you learnt about stack.
Constructing Mazes Write a Maze class for constructing, displaying, and solving mazes. All the mazes will be two-dimensional arrays of n rows and m columns. Each row, column cell is either open, or blocked by an internal wall. From any open cell, you may move left, right, up, or down to an adjacent empty cell. To solve a maze, you must find a path of open cells from a given start cell to a specified end cell. By default, you should assume that the start cell is in position (0, 0) and the end cell is at position (n-1, m-1).
To produce a new maze, your program should generate the maze dimensions and cell contents
randomly. The length and width are random number in the range (3-6) inclusive. The cell contents are either (0) or (1). Your maze class should be able to produce a new maze from the given parameters, print the maze to the terminal, find a path through the maze, and display the path if a solution exists. If no solution exists, your program should inform the user without crashing.
Below is a sample 6x6 maze with blue 1's indicating the location of walls and black 0's indicating open cells:
Start 0 0 0 0 0 0
1 1 1 1 0 1
1 0 0 0 0 1
1 0 1 1 1 1
1 0 1 0 0 0
1 0 0 0 1 0 End
A sample solution path from START to END is:
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 4), (2, 4), (2, 3), (2, 2), (2, 1), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3),
(4, 3), (4, 4), (4, 5), (5, 5)]
The red asterisks below show the path.
Start 1 2 3 4 5 0
1 1 1 1 6 1
1 10 9 8 7 1
1 11 1 1 1 1
1 12 1 16 17 18
1 13 14 15 1 19 End
Your program must have the following features:
1. Generate the maze parameters randomly
2. Print the maze to the terminal
3. Find a path in the maze from the START to the END
4. If no path exists, display an appropriate message
5. If a path exists, display the following
Mark the path from START to END with increasing numbers
The total length of the path
Sample of the output:
This program will attempt to find a path through an m by n maze.
Reading the file to generate the maze...
Initial Maze:
--------------
0 1 0 0 0
0 1 0 0 0
0 0 0 0 0
1 1 1 0 0
0 1 0 0 0
Path through maze: [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4)]
Length: 9
Maze with path
--------------------
1 1 0 0 0
2 1 0 0 0
3 4 5 6 7
1 1 1 0 8
0 1 0 0 9
You need to implement the following classes:
• Stack
• Maze
• PathPositio
• TestMaze
Finding paths:
You should come up with an algorithm design that utilizes an appropriate data structure such as a stack and the maze classes. You should analyze your algorithm in terms of space and time complexity.
Along with your java source code, you should write a report. This report should contain a brief summary of your results, including a discussion of the advantages/disadvantages of using a stack to solve this problem. Give a brief explanation of the big-Oh run-time of your methods as mentioned above. Also include any known problems/bugs in your code.
