$1$ Group$-$Specific Information

This assignment is to be done as a team of two $($including the Blackboard submission$).$ Groups are self$-$

selected. The same grade will be given to both members of each team.

$2$ Introduction

Many films and televisions shows involve literal or metaphorical mazes and the disorienting complexity of

navigating them. For example, in the real world, tens of thousands of robots plan efficient delivery routes

through Amazon's vast labyrinthine warehouses. In addition, the given maze involves literal or metaphorical

portals that enable teleportation between distant locations, as the video games. $($In the real world, there are

no such things.$)$

In this homework you'll implement a maze$-$solving function $($Dijkstra$\text{'}$s Algorithm$)$ class. Both the input

maze and output solution use an ASCII art "map" format $($see Sections $5$ and $6).$

$3$ Instructions

The following files have been given to you:

A file $($Maze$.$java$)$ declaring and implementing the solve$()$ function solving the given maze.

A file $($Vertex$.$java$)$ implementing the Vertex class.

A file $($Pair$.$java$)$ implementing the Pair class.

A file $($MainTest$.$java$)$ containing a main function with tests.

Download the files through blackboard. Finish Maze.java that implements function solve$()$ so that the

provided files compile into a program that runs with no failed tests. Submit the source files Maze.java.

$4$ Submission and Grading

Submit the aforementioned source file$($s$)$ via Blackboard as attached file$($s$).$ In the case of multiple submis$-$

sions, the last submission before the deadline is graded.

For grading, each submission is compiled with the provided files and run. Submissions that do not run

to completion $($i$.$e$.$ fail to print "Assignment complete."$)$ receive no credit. Submissions that take an

unreasonable amount of time $($e$.$g$.$ more than a minute or so$)$ to run and do not meet the asymptotic

efficiency requirements receive no credit. All other submissions receive full credit.

See the course late work policy for information about receiving partial credit for late submissions.

$5$ Maze String Format

Each maze is represented as a string with the following format:

The maze consists of several lines of the same length, each terminated by the $\text{'}\frac{\frac{?}{?}}{?}\text{'}($newline$)$ character.

Excluding these newline characters, all characters are either $\text{'}$#$\text{'}($hashtag$),\text{'},($space$),$ or digits

$({?}^{\text{'}},{?}^{\text{'}},9^{\text{'}}).$

The hashtag character denotes a wall.

The space character denotes an empty location.

A digit denotes a portal opening. Each such digit appears exactly twice, denoting the two locations

connected by the portal. The distance between these two locations via the portal is equal to the digit's

value $($e$.$g$.,$ the distance between the $\text{'}3\text{'},$ portal openings is $3).$

The boundary of the maze is the first and last row and column. All characters in the boundary

are hashtags, with the exception of two characters $($either spaces or digits$).$ These two non$-$hashtag

boundary characters are the exits of the maze.

For instance, the maze represented as the string

$"$# ######

# $17$#

########

#$17$#

### ####

$"$

which prints as:

contains two portals: the $\text{'}1\text{'}-$portal and the $\text{'}7\text{'}-$portal. The distance between the openings of the $\text{'}1\text{'}-$

portal via the portal is $1.$ The distance between the openings of the $\text{'}7\text{'},-$portal via the portal is $7.$

$6$ Maze Solution Format

A maze solution is represented as a string identical to that of a maze, but with $\text{'}$o$\text{'}($lowercase letter O$)$

symbols denoting a shortest path between two used portal locations and other locations, respectively, visited

along a shortest path between the two exits of the maze. A shortest path consists of a minimum$-$length

sequence of locations, each above, below, left, right or portal$-$adjacent to the previous, beginning and ending

with the locations of the exits. A solution to the maze above is

$"$#o######

#oooooo#

########

#ooo #

###o####

$"$

which prints as:

#o#####

#o$$oooo#

#######

#$$oo #

###O###

Note that valid solutions must be shortest paths. Thus the following, while it is a valid path connecting the

exits, is not a solution:

now i have four files Main $,$ vertex, pair and maze

where i can only write code in maze in java only

main code$----------------------------$

public class MainTest $\{$

public static void main$($String$[]$ args$)$

$\{$

$//$ Setup

String maze, soln;

Maze sol $=$ new Maze$()$;

$//$ Test a few mazes without portals

maze $=""$;

maze $+="$##### #

$"$;

maze $+="$# #

$"$;

maze $+="$# #####

$"$;

soln $=""$;

soln $+="$#####o#

$"$;

soln $+="$#ooooo#

$"$;

soln $+="$#o#####

$"$;

test$($sol$.$solve$($maze$).$compareTo$($soln$)==0)$;

maze $=""$;

maze $+="$##### #

$"$;

maze $+="$# # #

$"$;

maze $+="$# # # #

$"$;

maze $+="$# # #

$"$;

maze $+="$# #####

$"$;

soln $=""$;

soln $+="$#####o#

$"$;

soln $+="$#ooo#o#

$"$;

soln $+="$#o#o#o#

$"$;

soln $+="$#o#ooo#

$"$;

soln $+="$#o#####

$"$;

test$($sol$.$solve$($maze$).$compareTo$($soln$)==0)$;