1. Solving a Maze. Your program will read in a text file which has 2 numbers on the first two lines. The first number is the number of columns and the second number is the number of rows in the maze. The numbers will be followed by a grid of Xs and Os. The Xs represent walls while the Os represent pathways. The first row of the grid will have an S to mark the starting point, and the end will be marked with an E. There is only ONE correct path from S to E. Your program must find that pathway. Once your program finds the correct path you must replace the correct path by replacing only the correct Os with dashes (-).

8

7

SOXXXXXX

XOXXOXXX

XOOOOOOX

XOXOXXOX

XOXOXXOX

XXXOXXOX

XXXOOXOE

For the above input the following should be the output on the screen when the program finishes:

S-XXXXXX

X-XXOXXX

X------X

XOXOXX-X

XOXOXX-X

XXXOXX-X

XXXOOX-E

Recursion will help you solve the maze as you can recursively look in every direction. You may choose to change the S and E to - as well, and you will still get full marks. Assume there will always be a correct solution, and that there will be an S in the top row.

This program will make use of many of the skills you have learned in this course (reading from file, 2D array/arrayList, recursion).

*FOR CHEGG EXPERT:

****NEEDS TO BE DIFFERENT FROM PREVIOUS ANSWER TO THIS QUESTION****