Reference no: EM131369516
Assignment
In this question, you will test, using a backtracking algorithm, if a mouse can escape from a rectangular maze.
The backtracking algorithm helps the mouse by systematically trying all the routes through the maze until it either finds the exit or exhausts all possible routes (and concludes that the mouse is trapped in the maze). If the backtracking algorithm finds a dead end, it retraces its path until it reaches a position from which there is an untried path. The backtracking algorithm always tries all directions from any position, and always in the same order.
The input to the algorithm is a maze with walls (represented by '1' characters) and open passage ways (represented by '0' characters). The starting position of the mouse is represented by 'm' and the exit from the maze by 'e'. Your program should read the maze in from a file, and the name of the file should be a command-line argument. The first line of the input will contain the number of rows and the number of columns in a maze. Thus, the input might look like the following:
|
6
|
5
|
|
|
1
|
1
|
1
|
1
|
1
|
|
1
|
0
|
0
|
e
|
1
|
|
1
|
1
|
1
|
0
|
1
|
|
1
|
m
|
1
|
0
|
1
|
|
1
|
0
|
0
|
0
|
1
|
|
1
|
1
|
1
|
1
|
1
|
The maze will always have a wall around the outside, so you need not be concerned about the mouse falling off the maze as it explores all directions.
The backtracking algorithm keeps a stack of positions that are the beginnings of paths it has yet to try. From the current position, the algorithm pushes onto the stack any untried open neighboring positions (if there are any), always looking forward, backward, left and right from the current position. At each step, the algorithm pops the top position off the stack and pushes the untried neighboring positions onto the stack. The algorithm must mark each visited position with a period to avoid revisiting positions --- so that it will not loop forever trying the same routes.
The backtracking algorithm works as follows:
Because the backtracking algorithm needs a stack, you should implement a stack class (or you can use that from COSC 2006). Each item in the stack is the position of a cell in the maze --- that is, the row and column number of the cell.
Your program should print out the maze after each cell is visited, showing which cells have already been visited. Finally, your program must print out a message indicating whether the exit was found or that no route to the exit could be found (the mouse is trapped).
To develop your program, you can use the input file testMaze.txt, which contains the above maze.
Attachment:- MazeTest.txt
|
Computer is able to check the entire population of pencils
: New computerized systems are able to check for defects on products right on the assembly line. For example: a pencil manufacturer is able to use laser scanning to check for the size of the pencils. Since the computer is able to check the entire popul..
|
|
Inventories and inventory management
: Inventories - and inventory management - should be a thing of the past. An efficient and effective organization should be able to employ lean and just-in-time concepts so that inventories are not necessary. Do you agree or disagree with this statemen..
|
|
What organizing to implement vertical integration means
: Please explain in detail what "Organizing to implement vertical integration" means and how it involves organizational structure, management controls and compensation policies.
|
|
Dictum of management theory
: It has long been a dictum of management theory that leaders must adapt their behavior to fit the specifics of a situation. Discuss whether transformational leadership is appropriate for all occasions. In which situations might it not be effective and..
|
|
Backtracking algorithm
: COSC 2007 -Data Structures - The backtracking algorithm helps the mouse by systematically trying all the routes through the maze until it either finds the exit or exhausts all possible routes
|
|
What are difference between discrete and continuous variable
: qnt 275-What are the differences between quantitative and qualitative variables? What are the differences between discrete and continuous variables.
|
|
What is the probability
: Assume that 2% invest in both kinds. If an investor is chosen at random, what is the probability that this investor has either public or corporate funds?
|
|
What will be the price level of the overall economy
: ECON 3123- Suppose that the economy consists of two types of firms. Flexible price firms, who set prices P + a(Y - Y¯), and sticky price firms, who set prices E(P). Fraction s of the firm population is sticky. What will be the price level of the o..
|
|
Probability that randomly chosen user could not use a device
: If there were 18 million users of handheld data devices of this kind on that day, what is the probability that a randomly chosen user could not use a device?
|