Traverse a maze recursively. Your program MUST read from a file called "maze.dat".

A sample (Links to an external site.)maze has been provided. The actual maze will be larger. The start and end of the maze are represented with the characters + and -, respectively. The first line of the maze file will be the number of rows and columns, respectively.

As your program moves through the maze the current path should also be marked with the + character. Any path leading to a dead end should be marked with the . character.

Upon reaching the end of the maze your program should print a message to the screen stating that the maze was solved. If your program does not find the exit this should also be stated. All messages, and a print out of the solution, if one is found, should be to the screen.

Here is the actual maze file that will be used to test your programs.

47 131 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX + X X X X X X X X X X X X X X XXX X X X X X X XXX X X XXXXX X XXX X X XXXXXXX X XXXXXXX XXX X XXX X X XXXXX X X XXX X XXX XXXXX XXXXXXXXXXX X X X XXXXXXXXX XXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXXXXXX X XXX X X X X X XXXXX X X X X XXXXXXXXXXX XXXXX XXXXX XXX X XXX XXXXX X XXXXX XXX XXXXXXX X X X X XXX XXX XXX XXXXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXXXXXXXX XXXXXXX X X XXXXX XXX XXXXX XXXXX X X XXX X XXXXX XXXXXXX X XXXXX X X X XXXXX XXX XXX X X X XXXXX X XXXXX XXXXXXXXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXX XXX X XXXXXXX XXX X X X XXX XXX X XXXXX X X XXX X XXX X XXXXXXX X XXXXXXXXX X XXX X X XXXXX XXX XXXXXXXXXXXXXXX XXX X XXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXX XXXXXXX X XXXXXXX X X X XXXXXXX XXXXXXX XXXXX X XXXXXXXXXXXXXXX X XXX XXXXX XXX X XXX XXXXX XXXXXXX XXX XXX X XXX X XXXXX XXXXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXXXXXX X XXX XXXXXXX X X XXXXX X X X X XXX X X XXXXX X XXXXXXX XXX XXXXXXXXXXXXXXXXXXXXX XXXXXXX X XXX XXX X XXX X XXX XXXXXXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXX X XXXXXXXXXXX X XXXXX XXX X X X X X XXXXX X XXXXX XXXXX X X XXXXXXXXX XXX X X X X X XXXXX X X X XXX XXX XXXXXXXXXXXXXXXXXXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXXXXXXXX X XXXXXXX XXXXX XXXXXXX X XXX X XXX X XXXXXXXXXXX X XXX XXXXXXXXXXX XXX XXXXXXX X X X X X X X X XXX XXX X XXXXXXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXX XXX X XXXXXXX X XXXXX XXX XXX X X XXX XXX X XXXXXXXXXXXXXXXXX X X XXXXXXX XXX X X X X XXX X XXXXX X X XXX X X XXXXXXX X XXXXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXX XXXXX XXXXXXX X XXXXXXXXX XXXXX X XXXXXXXXX X XXXXXXXXXXXXXXXXX X XXXXXXX XXXXXXX XXX X X XXXXXXX X XXX X XXX XXXXX XXX X XXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXX X X XXXXX XXX X XXXXXXXXXXX XXX X X X X X X XXXXX XXX XXX XXXXX X X X X X X XXXXX XXX XXXXX X X XXXXXXXXXXX XXXXXXX XXX XXXXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXXXXXX XXXXXXXXX X X XXX X XXXXXXXXXXX XXX X XXXXXXXXX X X X X X X XXX X XXXXX X XXXXXXXXXXXXX X XXX XXX X X XXXXXXXXXXXXX XXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXXXX XXXXXXX XXXXX X X XXXXX X X XXX XXX X X X XXX X XXX X X XXXXXXX X X XXX X X X X XXX X X X X XXX XXXXX X XXX XXX XXX XXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXX XXX XXX XXXXXXXXX X X XXXXX XXX XXXXXXXXX X XXXXXXX XXXXXXX X X XXX XXXXXXX XXX X X X XXXXX XXX XXXXXXX XXXXXXXXXXXXXXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXXXXXX XXX X X XXX XXXXX X X XXXXX XXXXXXXXXXX X X XXX X X XXX XXXXXXXXXXXXXXX XXX X X XXX X X X X XXXXXXX XXXXX X X XXXXX XXXXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXX X XXXXX XXXXXXXXX X X X X XXX XXXXX XXX X X X XXXXXXXXX XXX XXXXXXXXX X XXX XXX XXX X X X X XXXXXXXXX X XXX X XXXXX XXX XXXXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXX XXX X XXX XXXXX X X X XXX XXXXX XXX X XXXXX XXXXX XXXXXXXXX XXXXX X XXXXXXXXX XXX X X XXXXXXX X XXX X XXX XXX XXXXXXX XXXXXXXXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXXXX XXX XXXXXXX X X XXX XXX X XXXXXXXXX XXXXX X XXXXXXX X XXXXXXXXXXX X XXX XXXXXXXXXXXXX X XXX XXX X X XXXXXXXXX X XXX XXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXXXX XXX X X XXX X XXX X XXX X XXXXX XXXXXXX XXXXXXXXXXXXXXXXX X XXXXX X X X XXXXXXXXXXXXXXX X X XXXXXXX X XXXXXXX XXXXX XXXXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXX XXXXX X X XXX X XXX X XXX X X XXXXX X X X XXX XXX X X X X XXXXX X X XXXXX X XXXXXXX X XXX X X X XXXXXXXXXXXXX XXXXXXX XXXXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXX XXX XXXXX XXX X XXX X XXX X XXX X X X X XXXXXXXXXXXXXXX X XXX XXXXX XXX X XXXXXXXXXXXXX X XXX X X X X XXXXX XXXXX X X X XXXXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXX XXXXX X X X X X X X X XXXXX XXXXX X XXXXXXX XXXXXXXXXXX X XXXXX X X X XXX XXXXXXX X XXX X XXX XXX XXX X XXX X X X X X X XXXXX X X X X X X X X X X X X X X X X X X X X X X - XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Only submit one file named Main.java.