Write a program that searches through a maze to find a path from the beginning to...

  

Transcribed Image Text:

Write a program that searches through a maze to find a path from the beginning to the end. The maze will be a two-dimensional grid of locations, numbered by row and column. We could draw out a maze like this: 0 1 2 3 0 X X X X 1 E X 2 X S A maze is described by 3 things: the valid locations (places where it's okay to walk, indicated as an X in the figure above), the start location (indicated by S), and the end location (indicated by E). Your program should first read the number of valid locations in the maze, and the row and column of each valid location. It should then read the starting location and the ending location. For the maze pictured above, the input would be: 8 0 0 01 02 03 10 12 20 22 22 10 Your program should be iterative, not recursive. We will use a stack to simulate recursion. The stack forms a natural data structure for storing what has been visited in the past, and the stack makes it easy to go back to a previous decision and try a different location. This type of search is common in compute science, and is called depth-first search (DFS). The driver will contain the logic to solve the puzzle. It should start at the starting location, and is only allowed to visit locations that are valid (according to the input). At each stage, the solver should either move forward in some direction (right, down, left, or up) and push that new location on the stack, or it should back up one location by popping the current location off the stack. This continues until the solve has either reached the end location or it has become empty (indicating that there is no path from the start to the end). The stack should keep track of the locations that have been visited from the start until the current location (the current location should be the one on the top of the stack). Each step should look at the current location and use that location to produce a "neighbor" location. A neighbor location is a location (possibly invalid) which is one step away from the original location. For example, 22 is a neighbor of 1 2 If the neighbor is both a valid location, and is not currently on the path that has been traversed (on the stack), then it will be added to the stack for further exploration. If all the neighbors of the current location (on the top of the stack) have been visited, then that location is removed from the stack (this is called backtracking). The Location class contains both the coordinates of the location and the functionality for an iterator. A Location object is able to iterate over all of its neighbor locations. Please read the comments in the Location.java file for more details of how the iteration should work. Because the stack will contain Location objects, and each Location object is an iterator over its own neighbors, each Location object of the stack will know which of its neighbors is next. Input specification Input will consist of a positive integer, which is the number of valid locations. This will be followed by that many Locations, which form the list of valid Locations. After that will come the start and the end locations. The start location and the end location are guaranteed to be valid. Output specification If no solution to the maze exists, then the program prints: No solution found Otherwise, the program prints a solution in the following format: Solution found: 22 12 02 0 1 0 0 10 Note that the program should report only the first solution it finds, not every solution there may be. The solution the program finds is heavily dependent upon whether the Location class iterates properly over its neighbors. Write a program that searches through a maze to find a path from the beginning to the end. The maze will be a two-dimensional grid of locations, numbered by row and column. We could draw out a maze like this: 0 1 2 3 0 X X X X 1 E X 2 X S A maze is described by 3 things: the valid locations (places where it's okay to walk, indicated as an X in the figure above), the start location (indicated by S), and the end location (indicated by E). Your program should first read the number of valid locations in the maze, and the row and column of each valid location. It should then read the starting location and the ending location. For the maze pictured above, the input would be: 8 0 0 01 02 03 10 12 20 22 22 10 Your program should be iterative, not recursive. We will use a stack to simulate recursion. The stack forms a natural data structure for storing what has been visited in the past, and the stack makes it easy to go back to a previous decision and try a different location. This type of search is common in compute science, and is called depth-first search (DFS). The driver will contain the logic to solve the puzzle. It should start at the starting location, and is only allowed to visit locations that are valid (according to the input). At each stage, the solver should either move forward in some direction (right, down, left, or up) and push that new location on the stack, or it should back up one location by popping the current location off the stack. This continues until the solve has either reached the end location or it has become empty (indicating that there is no path from the start to the end). The stack should keep track of the locations that have been visited from the start until the current location (the current location should be the one on the top of the stack). Each step should look at the current location and use that location to produce a "neighbor" location. A neighbor location is a location (possibly invalid) which is one step away from the original location. For example, 22 is a neighbor of 1 2 If the neighbor is both a valid location, and is not currently on the path that has been traversed (on the stack), then it will be added to the stack for further exploration. If all the neighbors of the current location (on the top of the stack) have been visited, then that location is removed from the stack (this is called backtracking). The Location class contains both the coordinates of the location and the functionality for an iterator. A Location object is able to iterate over all of its neighbor locations. Please read the comments in the Location.java file for more details of how the iteration should work. Because the stack will contain Location objects, and each Location object is an iterator over its own neighbors, each Location object of the stack will know which of its neighbors is next. Input specification Input will consist of a positive integer, which is the number of valid locations. This will be followed by that many Locations, which form the list of valid Locations. After that will come the start and the end locations. The start location and the end location are guaranteed to be valid. Output specification If no solution to the maze exists, then the program prints: No solution found Otherwise, the program prints a solution in the following format: Solution found: 22 12 02 0 1 0 0 10 Note that the program should report only the first solution it finds, not every solution there may be. The solution the program finds is heavily dependent upon whether the Location class iterates properly over its neighbors.

Answer rating: 100% (QA)

import javautilScanner import javautilStack class Homework Help static class Location int i j Locationint i int j thisi i thisj j static final int STA... View the full answer