通过 [ DFS ](https://medium.com/swlh/solving-mazes-with-depth-first-
search-e315771317ae “DFS”) 算法，求解Maze的最短路径问题。
Problem Description
In this assignment, you are asked to find the shortest path to solve the maze
problem. A maze generator written in Python, which can be found on Moodle, is
provided for creating solvable m x n 2-dimensional mazes. The entry and exit
locations of the maze are set at the cells at (0,0), i.e., top left corner,
and (m-1, n-1), i.e., bottom right corner, respectively.
The maze generator uses the Cell and Maze classes to accomplish its tasks.
Each cell has up to 4 connecting neighbors at the east, south, west, and north
directions. Some cells have less than 4 neighbors. For example, the cell at
(0, m-1) has neighbors at its south (1, m-1) and (0, m-2) west only. Absence
of neighbor at a particular direction is represented by None. Such information
is stored in a 4-element list called neighbor in each instance the Cell class.
Whether there is a passage between two neighboring cells is recorded in
another list of Boolean values called wall.
Each instance of Maze is composed of m x n instances of Cell in terms of a
list of rows of instances of Cell, i.e., a list of lists. The generate()
method is used internally by the Maze constructor when a Maze instance is
created. The method uses a depth-first search to generate a solvable maze.
Additional code is included in the method to ensure each cell in the maze is
at least connected to one neighboring cell. A str() method is provided for
displaying a maze graphically.
Assignment Requirements
Students are required to develop a Python program to find the shortest path
that connects the start cell at (0,0) and goal cell at (m-1, n-1) of the maze
using the breadth-first search and the A* algorithms. The solvers may be
implemented as methods of the Maze class or in whatever ways a student thinks
appropriate. The two search algorithms to be implemented must use the Maze and
Cell classes. Students must NOT convert the maze data into other maze
representations. Special purpose Python modules such as NumPy and NetworkX are
not allowed to be used. The quality of the shortest path found by the two
algorithms in terms of the path length (which should be the same), the number
of moves that each search algorithm has taken, the average runtime required by
each of the algorithms for solving 50 problem instances of 20x20 mazes should
be discussed. Students also need to find out the average runtime required by
two algorithms for solving 50 instances of 8x8, 10x10, and 15x15 mazes, then
discuss the observed results in light of the theoretical worst-case time
complexity of the two algorithms found in books or on the Internet.
The main body of the report is limited to 8 pages which should describe the
program design with program fragments and relevant description, test results
(with the details given in an appendix if needed), and the algorithms’ run-
time behaviors. An illustration the proper working of the algorithm, and a
full listing of program code must be included in an appendix.
Submission Requirements
Submit the above-mentioned report and Python program (in .ipynb or .py
extension with brief comments), to Moodle.
Weighting and Assessment Criteria
Grading will be based on solution correctness and completeness, and efficiency
of the submitted solution including choice of appropriate data structures, as
well as the quality of the documentation.
