Write a findpuppy.java containing

USEMAZE: Using the opened input Scanner, returns a 2D array containing the characters that make up the maze. If you apply the

suggested method of continually reading and concatenating lines of input, while sequentially traversing a 2D array in

row major order, you can use a separate index variable that is set to 0 before the loops begin and only increment after

each character is copied from the String into the 2D

GETLOCATION:

Once the array is filled, you need to locate the start position and the current direction the puppy is traveling when first

entering the building. Depending on how you are solving this assignment, you will probably want to replace the S

which indicates the start position, with the first asterisk *. The direction would be related to which side of the maze on

which the S is found, i.e.

If on row 0, direction would be South (note, I avoid using down, as associated words such as left and right are only

clearly defined based on the current direction the puppy is traveling).

If on row 7 (Yes. This literal constant or magic number would be fine here as chess boards always have 8 rows and

8 columns, i.e. never a possibility or need to change it in the future. 7 is used, as the indexing of arrays start at 0), then

the direction is North.

If on col 0 (left side), the entry direction would be East.

If on col 7 (right side), the entry direction would be West.

You may also want to locate and return the Ending position (exit point containing the E) and replace the E with a

space.

Up to you about everything the recursive method will need to know. However, since much of this data is primitive and

methods can only return a single entity, you may need to consider creative means to pass so many primitives back to

main so main can send them on to the actual recursive maze path solution method. One possibility is to store the

row/column values in 2 element arrays. One for the start and one for the exit positions.

AMAZE:

Recursive solution to navigating the paths found within a given maze. Overall, needs to be passed the various data

(including the maze) needed and returns false for each recursive call unless the exit location is reached which should set

the variable used for the return statement to true.

Several approaches can be applied. However, fundamentally you need a:

Base Case: The currently passed Row and Column values indicate the mazes exit. Sets the return variable to true.

General (Recursive) Case: Based on the currently received row and column position, a move in 1 of 3 directions needs

to be made (obviously a fourth move option would simply return the puppy to the location from which he had just

come which you want to avoid). However, before making the next move, that move needs to be validated through a

call to canMove. If canMove returns true, then the location to where the move will be made needs to be assigned an

asterisk *. The move then is made by recursively calling doMaze by adding or subtracting 1 from one of the current

indices based on the direction the puppy needs to proceed. If doMaze returns false, you need to assign a minus

sign - to the attempted location and you proceed to another possible move. Each recursive call should assign the