CMPSC 16 Final Project (Maze Solver)
In this project, you will be asked to solve 10x10 ASCII mazes, that are generated by this website.
The start and finish positions are always at the same spot, and your program must find a right from the top left to the bottom right.
(Warning: When you copy/paste from the website the spacing may be messed up, we will provide sample input/outputs).

      +--+--+--+--+--+--+--+--+--+--+
                                 |  |
      +  +--+--+--+--+--+--+--+  +  +
      |                    |     |  |
      +--+--+--+  +--+--+  +--+  +  +
      |  |        |     |     |     |
      +  +  +--+--+  +  +--+  +--+  +
      |     |     |  |        |  |  |
      +--+--+  +--+  +--+--+--+  +  +
      |        |     |        |     |
      +  +--+  +  +  +--+--+  +--+--+
      |  |     |  |        |        |
      +  +  +--+--+--+--+  +  +--+--+
      |  |              |  |        |
      +  +--+--+--+--+--+  +--+--+  +
      |  |                    |     |
      +  +  +--+--+--+--+  +  +  +--+
      |  |  |     |        |     |  |
      +  +  +  +  +--+--+--+  +  +  +
|     |  |              |
      +--+--+--+--+--+--+--+--+--+--+

    

Fig. 1 Example input.


    +++++++++++++++++++++
                      | |
    + +++++++++++++++ + +
    |             |   | |
    +++++++ +++++ +++ + +
    | |     |   |   |   |
    + + +++++ + +++ +++ +
    |   |   | |     | | |
    +++++ +++ +++++++ + +
    |     |   |     |   |
    + +++ + + +++++ +++++
    | |   | |     |     |
    + + +++++++++ + +++++
    | |         | |     |
    + +++++++++++ +++++ +
    | |             |   |
    + + +++++++++ + + +++
    | | |   |     |   | |
    + + + + +++++++ + + +
|   | |         |
    +++++++++++++++++++++
    

Fig. 2 Parsed Input.


    Maze solved:
+++++++++++++++++++++
●●                | |
+●+++++++++++++++ + +
|●●●●●●●●●●●●●|   | |
+++++++ +++++●+++ + +
| |     |●●●|●●●|   |
+ + +++++●+●+++●+++ +
|   |   |●|●●●●●| | |
+++++ +++●+++++++ + +
|     |  ●|     |   |
+ +++ + +●+++++ +++++
| |   | |●●●●●|     |
+ + +++++++++●+ +++++
| |         |●|     |
+ +++++++++++●+++++ +
| |          ●●●|   |
+ + +++++++++ +●+ +++
| | |   |     |●●●| |
+ + + + +++++++ +●+ +
 |   | |         |●●●●●
+++++++++++++++++++++

    

Fig. 3 Solved Maze.



Your Assignment
You will be given a maze file (Example input), and are asked to complete the following tasks.

1. Write a parser that will read in the maze and store it in memory in a way that can be used to find a path.

2. Write a print function that will display this represation

3. Write a function that will find a path through the maze. (See Fig 2)
(Hint: recursion is probably the right answer.)

4a. Print the solution. (See Fig 3)

4b. Print out the moves that a robot woudl have to take solve the maze (R - Right, L - Left, U - Up, D - Down).

Moves from beginning to end: R D D R R R R R R R R R R R R D D R R D D L L L L U U L L D D D D D D R R R R D D D D R R D D R R D D R R R R



5 (Extra Credit). You can get extra credit if you can support sizes other than 10x10.

Grading
Parsing the maze: 20%
Printing the initial maze: 10%
Solving the maze: 20%
Printing the moves from beginning to end: 10%
Written Report: 20%
Code style: 20%
Supporting any size maze: +10% (Extra)


Example


      $ ssh [your username]@csil.cs.ucsb.edu
      $ cd /cs/student/cspensky/cs16/maze/
      $ ./maze
      Reading in maze....
      +++++++++++++++++++++
                        | |
      + +++++++++++++++ + +
      |             |   | |
      +++++++ +++++ +++ + +
      | |     |   |   |   |
      + + +++++ + +++ +++ +
      |   |   | |     | | |
      +++++ +++ +++++++ + +
      |     |   |     |   |
      + +++ + + +++++ +++++
      | |   | |     |     |
      + + +++++++++ + +++++
      | |         | |     |
      + +++++++++++ +++++ +
      | |             |   |
      + + +++++++++ + + +++
      | | |   |     |   | |
      + + + + +++++++ + + +
      |   | |         |
      +++++++++++++++++++++
      Maze solved:
      +++++++++++++++++++++
      ●●                | |
      +●+++++++++++++++ + +
      |●●●●●●●●●●●●●|   | |
      +++++++ +++++●+++ + +
      | |     |●●●|●●●|   |
      + + +++++●+●+++●+++ +
      |   |   |●|●●●●●| | |
      +++++ +++●+++++++ + +
      |     |  ●|     |   |
      + +++ + +●+++++ +++++
      | |   | |●●●●●|     |
      + + +++++++++●+ +++++
      | |         |●|     |
      + +++++++++++●+++++ +
      | |          ●●●|   |
      + + +++++++++ +●+ +++
      | | |   |     |●●●| |
      + + + + +++++++ +●+ +
      |   | |         |●●●●●
      +++++++++++++++++++++
      Moves from beginning to end: R D D R R R R R R R R R R R R D D R R D D L L L L U U L L D D D D D D R R R R D D D D R R D D R R D D R R R R
    




References
Maze Generator