Graph Modeling Project)
1 Deliverables
1.1 Problem Modeling[40 pts]
• [10] Explain how you modeled the problem as a graph (typically, a few sentences)
• [10] Draw enough of the resulting graph to convince us that you have modeled the graph correctly (you don’t have to draw the whole graph).
• [10] Identify the graph algorithm needed to solve the problem (one sentence).
• [10] Convince us that this algorithm will actually solve the problem. This means that it will find a path if one exists (typically, a few sentences, depending on your approach).
1.2 Code Submission [25 pts]
Please include your code in the report. 10 points will be allocated for quality and readability of the code. The code should read in the provided input file and print the output.
1.3 Results [35 pts]
Display the output of your program on the input maze provided below. Points will be awarded for finding a correct path and printing it in the required format.
1.4 Extra Credit [5 pts]
2 Input Format
Your code will first read the input from a file, which is specified as follows: the first line contains a pair of integers representing the number of rows and columns, respectively, in the grid (both are 7 in our example). Each subsequent line describes the contents of a square in the grid and contains (i) the row number, (ii) the column number, (iii) the color of the arrow (R, B), (iv) whether the arrow is Circled or Not (C, N) and (v) the direction of the arrow (N, E, W, S, SE, SW, NE, NW).
For example, the second input line indicates that the (1,1) square contains an uncircled red arrow pointing to the East. The entire input file is included below. The last line corresponding to the target (7,7) square contains an X in the last three fields.
7 7 1 1 R N E 1 2 B N W 1 3 B N NW 1 4 R N NW 1 5 R N S 1 6 B N SW 1 7 B C S 2 1 R N SE 2 2 B N S 2 3 R N SE 2 4 B N S 2 5 R N N 2 6 R N NW 2 7 R N NE 3 1 B N E 3 2 R C N 3 3 R C S 3 4 B N E 3 5 B N N 3 6 B N S 3 7 B N NE 4 1 R N N 4 2 R N NE 4 3 B C E 4 4 R N SW 4 5 R N N 4 6 B N E 4 7 B N SW 5 1 B N W 5 2 R N S 5 3 B C W 5 4 R N SW 5 5 B N S 5 6 B N SE 5 7 R N NE 6 1 R N SW 6 2 B N S 6 3 B N NW 6 4 R C W 6 5 R N SE
6 6 R N S 6 7 B N S 7 1 B N SW 7 2 R N N 7 3 B N E 7 4 R N SW 7 5 B N SE 7 6 B N NW 7 7 X X X
3 Output Format
(1,1) (1,6) (5,2) (6,2)
