Problem Statement Consider a maze made up of rectangular array of squares, such as the following...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Problem Statement Consider a maze made up of rectangular array of squares, such as the following one: XXXXXXXXXXXXX X XXXX X X X X XX X XX XX X X XX X X XX XXXXX X X XXXXXXXXXXXXX Figure 1--- A sample maze The "X" blocks represent a blocked square and form the walls of the maze. Let us consider mazes that have only one entrance and one exit, as in our example. Beginning at the entrance at the top left side of the maze, find a path to t exit at the bottom right side. You can move only up, down, left, or right. Square is either clear or blocked by an X character. Let a two-dimensional array represent the maze. Use a stack data structure to find a path through the maze. Some mazes might have more than one successful path, while others might have no path. Hints: The primary consideration is that if you reach a dead end, you need to be able to backtrack along the path to the point where you can try a different path. The stack data structure makes it possible to store the current path and backtrack if necessary. Every clear position visited in the current path is pushed to the stack and if a dead end is reached, the previous position is popped from the stack to backtrack. You need to have a loop that begins with the start position and pushes it into the stack then moves to a neighboring cell until either the goal position is reached, or the stack becomes empty. Make sure to mark each clear array cell you move to as visited to avoid checking it again and getting stuck in an infinite loop. For example, each array cell can have three different values: "X" for blocked, "V" for visited, and "*"* for clear. A dead end is an array cell whose all neighbors are either blocked or already visited. What you need to do: There are four files you should pay attention to: Position.java: a class to store the position of an array cell. It has two attributes: row and column along with their accessor and mutator methods. It also has an equal's method that checks for equality of two Position objects. Maze.java: a class to store a maze. It has 3 attributes: a two-dimensional character array which represents the maze, a Position object to represent the start location, and another Position object to represent the stop location. MazeSolver: This class contains one static method, solve. It accepts a maze and returns an array of Positions that is used to traverse the maze if the maze is solvable. If the maze is not solvable then an empty array is returned. o Keep in mind that stacks store objects in reverse order so be sure to return the position array in the correct order. Tester: a sample driver class which calls the traverse method on a maze in either the SolvableMaze, UnsolvableMaze, or HugeSolvableMaze files. These should be at the root of the project folder. You only need to implement the solve method in the MazeSolver.java class. This method receives the maze to solve as a parameter and returns an array of Position objects which stores a solution to the maze if such solution exists; otherwise, it returns an empty array. Note: There might be more than one possible solution to a maze, depending on the ordering in which the neighboring cells are visited at each location. You can do whatever order you want if the maze is solved. For instance, First move left, if the left neighbor is not clear, then move right, if the right neighbor is not clear, then move up, if it is not clear, then move down. You may create any additional helper methods to aid you. For instance, you may make a method to convert the stack to a necessary array. Just remember, when you grab the information from a stack you are getting in the reverse order you push them. You must solve the problem using a Stack. You may use the built-in stack library but use of any other data structure is prohibited apart from constructing the final Position array result. Recursion is also not allowed. What you need to turn in: You need to submit the MazeSolver.java file containing your implementation of the solve method. Rubric Stack is utilized Iterative solution Returns correct solutions to solvable mazes 10 Returns correct solutions to unsolvable mazes 10 Additional Notes and Helpful Hints First hint I have is to not be afraid of creating additional variables to store information. For instance, you must move up, down, left, and right (or north, south, west, and east). Creating Position objects to represent these movements is perfectly acceptable. You will also want to create an object that is the walker of the maze. This walker keeps the current position in the maze. Other than push, pop, and peek on the Stack class, isEmpty is also a useful method. The maze class contains a bunch of methods that is meant to help you. Read what the methods do and decide which ones you want to use for your solution. Read the code given to you FIRST before starting to write your code so you can utilize it. It is there to make your life easier, not harder. Try to translate what you want to do in terms of the stack operations. For instance, if you find yourself at a dead end then you want to move back to a previous position. This means you will need to first pop the top position, which contains the spot located at the dead end, then peek to see where you need to be. Your stack should be declared and initialized as such: Stack Give it a name new Stack (); where you can name it whatever you want. Moving in a two-dimensional array requires the following math: Move up (North) Row+ I Move down (South) Row - I Move left (West) Move right (East) Column-1 Column + 1 HUGE UNSOLVABLE MAZE 101 0 0 100 99 XXXXXXX XXXXX X X X X X X X X X X X X X X X X X XXX X XXX XXX X X XXXXXXX X XXX XXXXXXXXXXX XXXXXXXXXXXXX X XXXXXXXXX X X X X XXXXX X XXX X X X X XXX X X X X X X X XXXXXXXXX XXX XXX X XXX XXXXXXX X XXXXXXX x X Page 1 of 4 3 XXXX X X X X X X X X X XXX XXXX 2600 words X3X3 X X X X X X X XXX XXXXX XXX X X X XXX XXX X X XXX XXXX XXXXX XXX xxx x x X X X X X X X X X X X X x3 XXXXXXXXXXXX XXX X3 X X X X3 X X X X X XXX X XXXXX XXXXX X X XXXXXXX X X X XXX XXX X XXX X XXX X XXX XXX x3 X X X X x X X X XXX X X I X X X X x x XXXXXXX XXXXXXXXXX X X X X x3 X X X X X X X X SOLVABLE MAZE 21 0 0 19 20 XXXXXXXXX (XXXXXXXXX X X X X SAA VA X XXXXX X X XXXXX X X X X X X X X X XXX XXXXXXXXXXXX X X X X XXXXX XXX XXXX X X X X www. X X X KXXXX XXX X XXX XXX X X X X XX X X X X X XXXXXXX. XXXXXXX XX X X X X XXXXX XXX X X XXX X X X X XX UNSOLVABLE MAZE 21 0 0 19 20 . XXXXXX X X X XXXXX X X XXXXX XXX X X X X XX X X XXXXX X XXX XXX X X X XX XXX X XXXXXXXXXX X . X X X X X X X X X X X X X X X X X X XXX X XX X X X X X X X . X XXX ' X X X XXXXXX X Problem Statement Consider a maze made up of rectangular array of squares, such as the following one: XXXXXXXXXXXXX X XXXX X X X X XX X XX XX X X XX X X XX XXXXX X X XXXXXXXXXXXXX Figure 1--- A sample maze The "X" blocks represent a blocked square and form the walls of the maze. Let us consider mazes that have only one entrance and one exit, as in our example. Beginning at the entrance at the top left side of the maze, find a path to t exit at the bottom right side. You can move only up, down, left, or right. Square is either clear or blocked by an X character. Let a two-dimensional array represent the maze. Use a stack data structure to find a path through the maze. Some mazes might have more than one successful path, while others might have no path. Hints: The primary consideration is that if you reach a dead end, you need to be able to backtrack along the path to the point where you can try a different path. The stack data structure makes it possible to store the current path and backtrack if necessary. Every clear position visited in the current path is pushed to the stack and if a dead end is reached, the previous position is popped from the stack to backtrack. You need to have a loop that begins with the start position and pushes it into the stack then moves to a neighboring cell until either the goal position is reached, or the stack becomes empty. Make sure to mark each clear array cell you move to as visited to avoid checking it again and getting stuck in an infinite loop. For example, each array cell can have three different values: "X" for blocked, "V" for visited, and "*"* for clear. A dead end is an array cell whose all neighbors are either blocked or already visited. What you need to do: There are four files you should pay attention to: Position.java: a class to store the position of an array cell. It has two attributes: row and column along with their accessor and mutator methods. It also has an equal's method that checks for equality of two Position objects. Maze.java: a class to store a maze. It has 3 attributes: a two-dimensional character array which represents the maze, a Position object to represent the start location, and another Position object to represent the stop location. MazeSolver: This class contains one static method, solve. It accepts a maze and returns an array of Positions that is used to traverse the maze if the maze is solvable. If the maze is not solvable then an empty array is returned. o Keep in mind that stacks store objects in reverse order so be sure to return the position array in the correct order. Tester: a sample driver class which calls the traverse method on a maze in either the SolvableMaze, UnsolvableMaze, or HugeSolvableMaze files. These should be at the root of the project folder. You only need to implement the solve method in the MazeSolver.java class. This method receives the maze to solve as a parameter and returns an array of Position objects which stores a solution to the maze if such solution exists; otherwise, it returns an empty array. Note: There might be more than one possible solution to a maze, depending on the ordering in which the neighboring cells are visited at each location. You can do whatever order you want if the maze is solved. For instance, First move left, if the left neighbor is not clear, then move right, if the right neighbor is not clear, then move up, if it is not clear, then move down. You may create any additional helper methods to aid you. For instance, you may make a method to convert the stack to a necessary array. Just remember, when you grab the information from a stack you are getting in the reverse order you push them. You must solve the problem using a Stack. You may use the built-in stack library but use of any other data structure is prohibited apart from constructing the final Position array result. Recursion is also not allowed. What you need to turn in: You need to submit the MazeSolver.java file containing your implementation of the solve method. Rubric Stack is utilized Iterative solution Returns correct solutions to solvable mazes 10 Returns correct solutions to unsolvable mazes 10 Additional Notes and Helpful Hints First hint I have is to not be afraid of creating additional variables to store information. For instance, you must move up, down, left, and right (or north, south, west, and east). Creating Position objects to represent these movements is perfectly acceptable. You will also want to create an object that is the walker of the maze. This walker keeps the current position in the maze. Other than push, pop, and peek on the Stack class, isEmpty is also a useful method. The maze class contains a bunch of methods that is meant to help you. Read what the methods do and decide which ones you want to use for your solution. Read the code given to you FIRST before starting to write your code so you can utilize it. It is there to make your life easier, not harder. Try to translate what you want to do in terms of the stack operations. For instance, if you find yourself at a dead end then you want to move back to a previous position. This means you will need to first pop the top position, which contains the spot located at the dead end, then peek to see where you need to be. Your stack should be declared and initialized as such: Stack Give it a name new Stack (); where you can name it whatever you want. Moving in a two-dimensional array requires the following math: Move up (North) Row+ I Move down (South) Row - I Move left (West) Move right (East) Column-1 Column + 1 HUGE UNSOLVABLE MAZE 101 0 0 100 99 XXXXXXX XXXXX X X X X X X X X X X X X X X X X X XXX X XXX XXX X X XXXXXXX X XXX XXXXXXXXXXX XXXXXXXXXXXXX X XXXXXXXXX X X X X XXXXX X XXX X X X X XXX X X X X X X X XXXXXXXXX XXX XXX X XXX XXXXXXX X XXXXXXX x X Page 1 of 4 3 XXXX X X X X X X X X X XXX XXXX 2600 words X3X3 X X X X X X X XXX XXXXX XXX X X X XXX XXX X X XXX XXXX XXXXX XXX xxx x x X X X X X X X X X X X X x3 XXXXXXXXXXXX XXX X3 X X X X3 X X X X X XXX X XXXXX XXXXX X X XXXXXXX X X X XXX XXX X XXX X XXX X XXX XXX x3 X X X X x X X X XXX X X I X X X X x x XXXXXXX XXXXXXXXXX X X X X x3 X X X X X X X X SOLVABLE MAZE 21 0 0 19 20 XXXXXXXXX (XXXXXXXXX X X X X SAA VA X XXXXX X X XXXXX X X X X X X X X X XXX XXXXXXXXXXXX X X X X XXXXX XXX XXXX X X X X www. X X X KXXXX XXX X XXX XXX X X X X XX X X X X X XXXXXXX. XXXXXXX XX X X X X XXXXX XXX X X XXX X X X X XX UNSOLVABLE MAZE 21 0 0 19 20 . XXXXXX X X X XXXXX X X XXXXX XXX X X X X XX X X XXXXX X XXX XXX X X X XX XXX X XXXXXXXXXX X . X X X X X X X X X X X X X X X X X X XXX X XX X X X X X X X . X XXX ' X X X XXXXXX X
Expert Answer:
Related Book For
Linear Algebra And Its Applications
ISBN: 9781292351216
6th Global Edition
Authors: David Lay, Steven Lay, Judi McDonald
Posted Date:
Students also viewed these programming questions
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
Managing Scope Changes Case Study Scope changes on a project can occur regardless of how well the project is planned or executed. Scope changes can be the result of something that was omitted during...
-
Neutrons can be used in diffraction experiments to probe the lattice structure of crystalline solids. Since the neutron's wavelength needs to be on the order of the spacing between atoms in the...
-
How does predictive planting support decision making? Identify three decisions that you can support.
-
Solve the given problems. Is division associative? That is, is it true (if b 0, c 0) that (a b) c = a (b c)?
-
Repeat the calculations of Example 9.5, but for a total solution normality of 0.5. Data From Example 9.5:- For the Cu 2+ /Na + exchange with a strong-acid resin, show how the fraction CuR2 in the...
-
Book and liquidation value The balance sheet for Gallinas Industries is as follows. Additional information with respect to the firm is available: (1) Preferred stock can be liquidated at book value....
-
A monopoly water slide has demand of p(Q) = a - bQ, where p is the price per slide ("ride"), Q is the quantity of slides demanded, and a, b > 0. Fixed costs are F = 0 and constant marginal costs are...
-
Alpha Company receives.A note from one of its customers. It is a $20,000 60 day note at 9% interest (ordinary time). What will be the maturity value of the note when it is collected?
-
a.) none of the answers are correct b.) 102,100 c.) 22,000 d.) 93,200 Maxwell Corporation's relevant range of activity is 6,000 units to 11.000 units. When it produces and sells 9,000 units, its...
-
What are some examples of reading approaches or reading methods that are supported by the science of reading? Have you seen any of these methods or approaches used in the classrooms you have worked...
-
Discuss the origin and the focus of the "new international economic order."
-
You are the manager of R+D+I in a company with a focus on developing new products based on AI. Artificial Intelligence (AI) is the set of theories and techniques for developing machines capable of...
-
Is it possible for two people to communicate effectively if they don't speak the same language? Should everyone learn a second language?
-
What intricate functions do non-coding RNAs fulfill in the complex landscape of gene regulation, and could you elucidate specific examples of non-coding RNAs alongside their molecular mechanisms,...
-
a. Safron Corporation issued bonds in the amount of $70,000 that will be paid in four years. Interest of $7,000 is payable annually each December 31 with the first interest payment at the end of the...
-
Refrigerant R-12 at 30C, 0.75 MPa enters a steady flow device and exits at 30C, 100 kPa. Assume the process is isothermal and reversible. Find the change in availability of the refrigerant.
-
Solve A x = b and A(x) b, and show a that the inequality (2) holds in each case. A = 7 -5 10 19 Ab 10-4 -6 1 11 9 -4 1 0-2 7 -3 7 1 .49 -1.28 5.78 8.04 ,b= .100 2.888 -1.404 1.462
-
Prove the given statement about subsets A and B of R n , or provide the required example in R 2 . A proof for an exercise may use results from earlier exercises (as well as theorems already available...
-
Use the algorithm from this section to find the inverses of Let A be the corresponding n x n matrix, and let B be its inverse. Guess the form of B, and then prove that AB = I and BA = I. 1 0 0 1] 1 0...
-
In a hypothesis test the p value is 0.043. This means that we can find statistical significance at: (1) both the 0.05 and 0.01 levels (2) the 0.05 but not at the 0.01 level (3) the 0.01 but not at...
-
In testing the null hypothesis that p = 0:3 against the alternative that p 0:3, the probability of a type II error is ______ when the true p = 0:4 than when p = 0:6. (1) the same (2) smaller (3)...
-
An article states there is no significant evidence that median income increased. The implied null hypothesis is: (1) Median income increased. (2) Median income changed. (3) Median income did not...
Study smarter with the SolutionInn App