In this assignment, you are asked to complete a Java program that finds the shortest path that a hare needs to take to go through a grid-shape maze. The hare enters the maze from a specific square (start) and leaves the maze at another specific square (target). 1 Program Input and Maze Map The program starts by asking the user to enter the name of a txt file containing the maze map. The file needs to be a tab-delimited rectangular shape table with multiple rows and columns. Here is an example of input file and the maze it represents: Table 1: Example of input file S\t N\t R2\t N\t D3 N\t R1,D2\t N\t W4\t N N\t DE\t N\t N\t N N\t N\t XR, D2, W2\t D1,R1\t W1 N\t N\t XD\t XR\t N N\t N\t N\t N\t T column 0 column 1 column 2 column 3 column 4 START row 0 row 1 row 2 row 3 row 4 row 5 10.01 - As you see in the example, content of each table cell is a string str that can be interpreted in the following way: str.equals("S"): cell is the start square where hare starts the journey. This cell is always at row 0 and column 0 (unless you want to do the extra-credit part of the assignment). str.equals("T"): cell is the target square where hare ends the journey. This cell is always at the last row and last column (unless you want to do the extra-credit part of the assignment). str.equals("N"): cell has no special property. Hare can move either one square to the right or one square to the bottom of the map (unless you want to do the extra-credit part of the assignment). str.equals("DE"): cell is a dead-end which means that if hare enters this cell, there is no way out of it. str.contains("W"): cell is a waiting square! If hare enters this cell, it needs to stay and wait in the cell for a specific units of time before leaving it. The length of waiting time is determined by the number that comes after 'W' (e.g. "W5" means that hare needs to stay and wait for 5 consequent steps before moving out of the cell). str.contains("XR"): cell is a no-right square! If hare enters this cell, it can't exit by moving to the right square. !str.contains(XR") && str.contains("R"): cell has a ladder on it! If hare enters this cell, it can either move normally (one step to the neighboring squares) or use the ladder to move multiple squares to the right. The length of ladder comes after the letter 'R' (e.g. "R3" means that there is a horizontal ladder of length 3). str.contains("XD"): cell is a no-down square! If hare enters this cell, it can't exit by moving down. !str.contains("XD") && str.contains(D): cell has a ladder on it! If hare enters this cell, it can either move normally (one step to the neighboring squares) or use the ladder to move down multiple squares. The length of ladder comes after the letter 'D' (e.g. "D4" means that there is a vertical ladder of length 4, while R3,D4" means that there is a ladder that moves hare 3 cells to right and 4 cells to the bottom of the maze). 2 Finding the Shortest Path Given a maze, there may be many paths that allows hare to move from start to the target square. Some paths took longer than others. The goal of the program is to find the shortest path using the "Maze.solve" method available in the starter code. Example of Shortest Path in a Maze Consider the maze given in Table 1. There are many paths from start to target square. Below, you can find some of them and their corresponding lengths: (0,0) (1,0) (2,0) (3,0) (4,0) (5,0) (5, 1) (5, 2) (5,0) (5,1) (5, 2) (5,3) (5,4). Length: 9 (0, 0) (0, 1) (0, 2) (0, 4) (3,4) (3,4) (4, 4) (5,4). Length: 7 (0,0) (1,0) (1,1) (3,2) (3,2) (3,2) (5, 2) (5, 3) (5,4). Length: 8 (0,0) (1,0) (1, 1) (2, 1) dead-end. Length: . After considering all possible paths, the shortest path is the one with length 7 (second path. in the list). Recursive Solution The current draft of the method recursively solves the maze assuming that all of the maze cells with the exception of source and target are normal squares (i.e. hare can move to either the right or bottom neighbors). You need to manipulate the implementation of this method so that it can find the shortest path given a maze containing all kinds of squares (normal, waiting, dead-end, no-right, no- down and squares with ladders). Hint: only focus on manipulating Maze.solveHelper method. 11 12 13 14 15 16 17 again: 18 19 20 21 22 23 24 25 1 import java.io.File; 2 import java.util.ArrayList; 3 import java.util.Scanner; 4 5 public class Main { 6 7 8 9 10 06 1234567 private static Maze maze; private static ArrayList readInputFile(Scanner keyboard) { System.out.print( "Please enter the name (including extenstion and possibly path) of the txt file containing the map: "); Scanner file null; ArrayList map = new ArrayList (); do { try { file = new Scanner(new File(keyboard.nextLine())); } catch (Exception e) { System.out.print("Error: Something is wrong with the input file. Please try "); continue; } while (file.hasNextLine()) { map.add(file.nextLine().split("\t")); if (map.size() > 1 && map.get(map.size() - 2).length != map.get(map.size() - 1).length) { file = null; System.out.println("Error: map does not have a rectangular shape."); break; 26 } 27 } 28 29 30 31 32 null); 33 34 } 35 36 37 38 for (int r = 0; r < maze.getRows(); r++) 39 40 input.get(r)[c]; 41 42 43 44 45 46 47 48 49 else { 50 51 52 53 54 55 56 57 58 59 60 61 } 62 63 64 65 66 67 68 maze.addVerticalJump(r, c, -cell.nextInt()); return false; // wrong format if (map.isEmpty() || map.get(0).length System.out.println("Error: map is empty."); file = null; } while (file == return map; private static boolean interpretMap(ArrayList input) { maze = new Maze(input.size(), input.get(0).length); for (int c = 0; c < maze.getColumns(); c++) { String current = if (current.equals("N")) continue; else if (current.equals("S")) maze.addStart(r, c); else if (current.equals("T")) maze.addTarget(r, c); else if (current.equals("DE")) maze.addDeadEnd(r, c); if (current.contains("XD") ) maze.addNoDown(r, c); else if (current.contains("XU")) maze.addNoUp(r, c); else if (current.contains("D")) { Scanner cell = new Scanner(current.substring(current.indexOf("D") + 1)); cell.useDelimiter("[^0-9]"); try { maze.addVerticalJump(r, c, cell.nextInt()); } catch (Exception exp) { return false; // wrong format } else if (current.contains("U")) { Scanner cell = new Scanner(current.substring(current.indexOf("U") + 1)); cell.useDelimiter("[^0-9]"); try { } catch (Exception exp) { == 0 ) { 69 } 70 } 71 if (current.contains("XR")) 72 73 74 75 76 77 maze.addNoRight(r, c); else if (current.contains("XL")) maze.addNoLeft(r, c); else if (current.contains("R")) { Scanner cell = new Scanner(current.substring(current.indexOf("R") + 1)); cell.useDelimiter("[^0-9]"); 78 try { 79 maze.addHorizontalJump(r, c, cell.nextInt()); 80 } catch (Exception exp) { 81 return false; // wrong format 82 } 83 84 85 } else if (current.contains("L")) { Scanner cell = new Scanner(current.substring(current.indexOf("L") + 1)); cell.useDelimiter("[^0-9]"); 86 try { 87 maze.addHorizontalJump(r, c, -cell.nextInt()); 88 } catch (Exception exp) { 89 return false; // wrong format 90 } 91 } 92 93 94 if (current.contains("W")) { Scanner cell = new Scanner(current.substring(current.indexOf("W") + 1)); cell.useDelimiter("[^0-9]"); 95 try { 96 maze.addDelay(r, c, cell.nextInt()); 97 } catch (Exception exp) { 98 return false; // wrong format 99 } 100 } 101 } 102 103 104 } 105 106 107 108 109 do { 110 111 112 readInputFile(keyboard); 113 114 115 116 return true; // correct format public static void main(String[] args) { Scanner keyboard = new Scanner(System.in); ArrayList input = null; if (input != null) System.out.println("Error: Input file has wrong format!"); input = } while (!interpretMap(input)); maze.solve(); 117 maze.printSolution(); } 118 119 } 120 1 import java.io.File; 2 import java.util.*; 3 4 public class Maze { 456 class Cell { public boolean deadend = false, noRight = false, noLeft = false, noDown = = false, start = false, 7 8 target = false; public int horizontalJump = 0; 9 10 public int verticalJump public int wait = 0; = 0; 11 public int shortest = -1; // not yet discovered 12 public Cell nextStep; false, noUp 14 15 16 17 13 public int row, col; 3456 Cell(int row, int col) { this.row = row; col; this.col = 18 } 19 20 21 22 23 Cell(int row, int col, int wait) { this.row = row; this.col = col; this.wait = wait; 24 } 25 26 27 if (wait == 0 ) 28 29 public String toString() { II return "(" + row + ", + col + ")"; return new Cell(row, col, wait - 1).toString() + "->(" + row + + col + ")"; 30 } 31 } 32 33 private int rows, columns; 34 private Cell[] [] map; 35 36 public int getRows() { 37 return rows; 38 } 39 40 public int getColumns() { 41 42 } 43 44 45 46 47 48 49 50 51 52 53 return columns; public Maze(int rows, int columns) { this.rows = rows; this.columns = columns; map = new Cell[rows][columns]; for (int r = 0; r < rows; r++) } for (int c = 0; c