Description

Programming I Assignment: Maze

We represent a maze as a 2-dimensional array, where each element represents the corresponding cellin the following way. Each cell has 4 doors, and these doors can be either open or closed, corresponding to 0 and 1, respectively. Each cell can be represented as an integer. Figure 1(a) is an example of a 4x4 maze. Figure 1(b) is an example of a cell, in which the E-door is open and every other doors are closed. Figure 1(c) shows its bit representation is 1011. We can also convert it to a decimal number 11.

This way we can fully represent Figure 1(a) as the following 4x4 integer array.

Note that the maze is required to have the entrance on top left and exit on bottom right as shown in Fig 1(a). All numbers in the array must be non-conflicting. For example, you cannot have a an array a[][], in which a[1][2]'s E-door is open but a[1][3]'s W-door is closed. They are conflicting with each other. If these requirements are satisfied, then the input is legitimate.

What You Need to Do

Read in a m×n array representing a maze. First you need to check whether the input array is legitimate or not. If it is not, your program should simply output input error and terminate.

If the input is legitimate, then your program should output the path from the entrance to the exit door. Top-left position is (1,1). If there are more than one paths, you should output them in (increasing) lexicographical order. There will be at most two distinct paths in our test cases. If no such path exists, your program should output no way out.

Sample Input

4 4
12 11 12 13
5 9 2 4
1 0 12 5
7 7 3 2

Sample Output

(1,1)->(1,2)->(1,3)->(2,3)->(2,2)->(3,2)->(4,2)->(4,3)->(4,4)
(1,1)->(1,2)->(1,3)->(2,3)->(3,3)->(3,4)->(4,4)

Hint

You may need to use a stack to record your previous moves to the current location and another mxn array to record the locations you have visited (to prevent from looping forever). This is probably the easiest way. Alternatively, you can use recursion without using a stack, since recursion automatically uses the system stack. You may still use recursion, but we encurage you to use iteration instead of recursion, since recursion is actually harder in this case. There may be other ways to do this assignment, but they may be harder.

Grading Criteria

Correctness 70%

This will be checked by OJ just like our Lectures and Labs.

Program Style 30%

1. Your program should be well-commented. All variables, functions, loops should be clearly explained both in the source code and briefly in the README file.
2. Blocks in your source code should have proper indentation (縮排).
3. Do not use any global variable to pass data in and out of a function.
4. For a good program style, please follow Recommended C style and coding rules.

Submission

Submit your source code on OJ.

Input

4 4
12 12 12 13
5 9 2 4
1 0 12 5
7 7 3 3

Output

input error

Sample Input  Download

Sample Output  Download

Tags

Discuss