(Solved): ProblemThe maze is represented by a rectangular matrix of M * N.The shaded part indicates that ...
?Problem?
The maze is represented by a rectangular matrix of M * N.The shaded part indicates that this road cannot be passed?The blank part indicates that this road is passable. The rule is that you can only go up and down or go left and right just one step at a time. Design a program to find all paths from the entrance to the exit.
Fig1 Maze
?1?The specifications of the maze (i.e. the number of rows and columns), the status setting (i.e. whether each square can pass), and the positions of the entrance and exit shall be determined randomly by the input.
?2?The obtained path should be output as a linear sequence of coordinates of each grid on the path from entrance to exit. If there is no path, the information of no path should be printed.
?3? Find the shortest path from the entrance to the exit.
?Implementation tips?
?1?The maze can be convert into a graph, that is, the blank in the maze is regarded as the vertex of the graph, and the neighbors in four directions(up?down?left?right) of the blank which are blank are regarded as the undirected edge of the graph. The vertices of the graph store the blank coordinates of the maze. In this way, the maze shown in Fig. 1 can be converted into the maze shown in Fig. 2. Maze solving problem can be transformed into graph traversal problem.
?2?Storage structure: maze can be represented by two-dimensional array maze [] []. Row and col represent the number of rows and columns of the maze respectively. Maze [i] [j] represents a grid in row i and column j of the maze, maze [i] [j] = 0 indicates that the grid is passable, and maze [i] [j] = 1 indicates that the grid is not passable. You can add a circle of obstacles around the maze, which can ensure that you can choose four directions from any vertex.
?3?You can write Recursive algorithm or non recursive algorithm to find all paths.
?4?The breadth first search traversal algorithm of graph can be used to find the shortest path of maze.
?Data structures and algorithm?
?1?Traversal of graph?
?2?Recursive and non-recursive algortithm
1. Problem definition
Analyze the topic and describe the problem. Briefly describe the problems to be solved, the requirements and restrictions, and list the specific objectives to be achieved in this design .
2. Outline design
Define the corresponding data structure for the involved data objects, including logical structure, storage definition and main operations. Designed the main algorithms and the analyze the run time complexity.
3. Coding and test analysis
Enough test cases are used to illustrate that the program has completed the topic and achieved the design goal. Paste your output and test dataset?screenshot in your compiler?
4. Conclusion
Explain the problems and solutions in the process of system design and program debugging. You can write some improvement ideas on the system you have implemented.
