# 5. MAZE RUNNER Waking up one morning, we find ourselves in a maze, and no idea of how we got here. T

5. MAZE RUNNER Waking up one morning, we find ourselves in a maze, and no idea of how we got here. Trying to get out, we discover that the walls of the maze randomly move! Luckily, we can use our Java programming skills and write a program to help us find an exit. First, download this file and save it in the same folder as your solution http://courses.cs.tamu.edu/hurley/cpsc111/homework/MazeCreator.class This file contains two methods: public static int[][] generateMaze(int size) : Takes a size and returns a random maze as a 2D int array public static void printMaze(int[][] maze, int size): A utility function that takes as arguments the maze and the size and prints the maze to the screen In your program, first ask the user for the size of the maze. Then, use MazeCreator to generate a random maze and print it to the screen. In the maze, 1 represents a wall, 0 represents an open space. You will always start at position [size/2][0] (written as row,column). Next, write a method that given the maze, determines whether there is a path to any exit from the starting point. To do this, keep track of your position (row and column) and your moves. Use an ArrayList for your list of moves – this will make it easier to add/remove moves. If you reach a dead-end, backtrack your moves and try to go in another direction. Keep going until you reach an exit or return to the starting point with no more directions to explore. In the end, output whether you found an exit, and the list of all your moves (you dont have to match the exact format of the example below, just make your solution readable easily). Hint1: To help visualize your solution, try drawing out a sample maze and trace how your program should execute. Hint2: The exit will always be on the right side of the maze Hint3: Keep track of where you have been by changing the value of the space in the maze. (In the examples below 9 is used to identify the visited path) EXAMPLE OUTPUT OF 2 EXECUTIONS: ———————————————————————— Enter size: 10 Maze (size = 10, start = (5, 0), 1 = wall, 0 = open path): 1111111111 –> EXIT 1111111111 –> EXIT 1111111111 –> EXIT 1111100111 –> EXIT 1101100111 –> EXIT START –> 0000000011 –> EXIT 1111111011 –> EXIT 1111111000 –> EXIT 1111111001 –> EXIT 1111111000 –> EXIT 5, 0 RIGHT 5, 1 RIGHT 5, 2 RIGHT 5, 3 RIGHT 5, 4 RIGHT 5, 5 RIGHT 5, 6 RIGHT 5, 7 DOWN 6, 7 DOWN 7, 7 RIGHT 7, 8 RIGHT Exit Successful! Maze (size = 10, start = (5, 0), 1 = wall, 0 = open path): 1111111111 –> EXIT 1111111111 –> EXIT 1111111111 –> EXIT 1111100111 –> EXIT 1101100111 –> EXIT START –> 0999999911 –> EXIT 1111111911 –> EXIT 1111111999 –> EXIT 1111111001 –> EXIT 1111111000 –> EXIT ———————————————————————— Enter size: 10 Maze (size = 10, start = (5, 0), 1 = wall, 0 = open path): 1111100000 –> EXIT 1111101111 –> EXIT 1110000011 –> EXIT 1110000011 –> EXIT 1100100100 –> EXIT START –> 0001110000 –> EXIT 1111111111 –> EXIT 1111111111 –> EXIT 1111111111 –> EXIT 1111111111 –> EXIT 5, 0 RIGHT 5, 1 RIGHT 5, 2 UP 4, 2 RIGHT 4, 3 UP 3, 3 RIGHT 3, 4 RIGHT 3, 5 RIGHT 3, 6 RIGHT 3, 7 UP 2, 7 BACK TO 3, 7 BACK TO 3, 6 DOWN 4, 6 DOWN 5, 6 RIGHT 5, 7 RIGHT 5, 8 RIGHT Exit Successful! Maze (size = 10, start = (5, 0), 1 = wall, 0 = open path): 1111100000 –> EXIT 1111101111 –> EXIT 1110000911 –> EXIT 1119999911 –> EXIT 1199109100 –> EXIT START –> 0991119999 –> EXIT 1111111111 –> EXIT 1111111111 –> EXIT 1111111111 –> EXIT 1111111111 –> EXIT Name your main class Hw5pr5 and your file Hw5pr5.java.