11781 - 231001_1/21_FinalProject
|
Time |
Memory |
| Case 1 |
1 sec |
32 MB |
| Case 2 |
1 sec |
32 MB |
| Case 3 |
1 sec |
32 MB |
| Case 4 |
1 sec |
32 MB |
| Case 5 |
1 sec |
32 MB |
| Case 6 |
1 sec |
32 MB |
| Case 7 |
1 sec |
32 MB |
| Case 8 |
1 sec |
32 MB |
| Case 9 |
1 sec |
32 MB |
| Case 10 |
1 sec |
32 MB |
Description
Rat in a Maze
Rat in a maze is a popular problem that utilizes backtracking, linked list or stack. A maze is a 2D matrix in which some cells are blocked. The representation of a maze is given as the following 2D array:
12
|
11
|
12
|
13
|
5
|
9
|
2
|
4
|
1
|
0
|
12
|
15
|
7
|
7
|
3
|
2
|
We represent this maze a 4×4 array, where each element represents the corresponding “cell” in the following way. Each cell has 4 “doors”, and these doors can be either open or closed. All doors in the maze are “static”, i.e. they do not change over time. The four doors of a cell are represented as N, E, S, and W, respectively. We use a 4-bit value to represent the status of the doors. For example, (1011) in binary or 11 (since 8+2+1) in decimal represents a cell with its E door opened and N, S, W doors are closed. That is, we use 0 represents the door opened and 1 represents the door closed. A 4×4 maze can be stored as a decimal-valued 4×4 array, where each corresponds to a number between 0 and 15. The W door of the top-left cell and E door of the bottom-right cell are always open, representing the entrance and exit of the maze. Note that the numbers of neighboring cells need to be consistent with each other.
Read in a m×n maze. There are 3 cases of output:
-
Output the shortest path from the entrance to the exit door. (There is only ONE shortest path.)
-
Output the inconsistent doors, such as sample 2.
-
If there is no path, print “There is no path.”
In this assignment, you need to use C++ to finish the final project and you need to create a structure and a class. Any kind of structure and class you can use and any place you can utilize the structure and the class.
Inconsistent: There is only ONE pair of inconsistent cell. Please put the smaller index of the cell in front of the other. You don’t need to check the boundary of the maze, since there will always exist doors except the entrance and exit of the 4 edges. (It is OK if you want to check the boundary in case.)
NOTE: The maze may be some special cases, you need to think about those cases and avoid time limit exceeded .
Input
Two integers m and n, and a m×n array
Output
See the sample output, remember to change a new line at the end.
Tags