Students will apply concepts of advanced Backtracking.

Your solution for each test case must run within $0\mathrm{.}31$ seconds.

Kenny is with his friends at the county fair. They got tickets to enter

in the magical corn maze. The maze consists of teleportation pads, that allow you jump through

various spots in the maze. Kenny is really scared to go in$,$ but his friends promise they will

always be together in the corn maze. Unfortunately, they got separated and now Kenny is alone

in the corn maze. Kenny is freaking out until he gets a text from his friend that they are waiting

for him to get to the end. They promise to guide Kenny to the end. However, his phone has a low

battery, so he must hurry $($or else he is trap there$).$ Kenny's friends remind him that there are

some magical teleportation pads within the maze that will help him get out fast before his phone

battery dies. However, there are some that can send Kenny to dead ends. Your goal is to get

Kenny out of the magical maze before his phone dies $($hence the running time constraint

restriction$).$

The Maze Files and Understanding the Maze Itself:

You are provided a total of $5$ text files. Inside each text file is a maze. Here is a sample below.

The number of rows and columns are all different in each text file, please do not assume

they are the same. However, I can assure you that the time limit will remain the same for

the grading. Meaning, the biggest maze provided will be the same size for when the

graders test your code.

The $\text{'}*\text{'}$ represents a valid space that Kenny can walk on$.$

The $\text{'}$@$\text{'}$ represents an invalid space that Kenny cannot walk on$.$ Think of it as an

obstacle.

The $\text{'}x\text{'}$ represents the exit square. This is basically the destination that Kenny needs to

get to be out of the magical maze.

Kenny can only walk in $4$ directions. Up$,$ down, left, and right. Diagonal moves are not

allowed.

The digits such as $\text{'}1,\text{'}\text{'}2,\text{'}3\text{'},$ etc... represent magical squares. These squares will

teleport you to other matching digit in the maze. For example, the $\text{'}\text{'}1\text{'}$ in the above figure,

if walked on$,$ will transport you to the other $\text{'}1\text{'}.$ It will NOT transport you to the different

digit spots.

Kenny will always start at the bottom left corner of the maze. That is the entry point

technically

Implementation Details:

You are going to create a Class called MagicMaze.

The MagicMaze Class must have the following attributes:

a$.2D$ primitive char array that will store the entire input maze from the provided

text file.

b$.$ A String object that stores the maze number $($maze$1,$ maze$2,$ etc...$)$

c$.2$ primitive integers that each hold the number of rows and columns in the $2D$

maze

d$.$ You are welcome to add additional attributes that feel may be necessary.

The MagicMaze Class has one overloaded constructor with three parameters.

a$.$ A String Object that represents the name of the maze text file

b$.$ A primitive int that represents the number of rows.

c$.$ A primitive int that represents the number of columns.

The MagicMaze Class must have some method that will perform scanning the maze from

the provided text file into the respective class attribute.

The MagicMaze Class has a non$-$static method called solveMagicMaze, which will be the

actual problem solving $($getting Kenny out of the maze$)$ that you will need to implement.

The method returns a Boolean value. If the value is true, then the maze was solved

successfully, otherwise the maze was not solved successfully. You must use

Backtracking to solve this maze. I would recommend creating a recursive method like

the $N-$Queens problem we did in class.

You are given $5$ test mazes inside the provided text files. All text files are in the same

directory as the driver and solution file you are going to implement. DO NOT CREATE

SUBFOLDERS!

You must use Backtracking in your implementation.

Do NOT use any Graph Algorithms.

You are welcome to create helper methods in your solution class, but please do not

modify the driver class in any way. This will result in your code not working properly

when grading, which will result in points being deducted that are not going to be given

back.

A driver file $($MagicMazeDriver$.$java$)$ has been provided for you

to show you how the methods are called along with a test case based on maintaining the given

maze. you will notice the main method uses the args parameter. In order to

test your file when running your code you will need to type some extra things into the terminal.

Besides typing java and the name of the class you want to run, you will need to include text file

to be read, the number of rows, and the number of columns. For example, java

MagicMazeDriver maze$4.$txt $1520$ will run the driver class along with sending the

respective text file to be solved, the number of rows in that particular maze, and number of

columns as well.

this is the driver file:

import

java.io$.$ File;

import java.util.scanner;

public class MagicMazeDr