Data Structures
Stonehill College CS 211
CS 211
Data Structures
Stonehill College CS 211
DUE
October 11, 2007
1. prog2a.cpp
We return to the mouse in the maze. Your job is to help Algernon find his way out of the maze
Input to your program, should be a representation of a maze, like the one pictured below. The two numbers above the maze represent the number of rows and columns. Also, the maze has a wall of 1's surrounding it (as we discussed in class).
10 10
1111111111
1m00100001
1101101101
1000101101
1100001101
1111110001
1111000111
1111010001
11110001e1
1111111111
Output is a path through the maze, marked by X's-- the path may not be the most direct one but every x must be an a valid path out of the maze. There may be more than one path-- just find one.
1111111111
1mX01XXXX1
11X11X11X1
10XX1X11X1
110XXX11X1
111111XXX1
111100X111
111101XXX1
11110001e1
1111111111
done
Notes:
You should read your input from a file maze.txt. The input file will contain a single maze. Output is to the screen.
If no path exists, you should print the maze and the message: "Trapped -- No Way out!"
You may assume all input is correct
Use a stack. The algorithm from class is a start, but you will have to add a bit.
You should have a Maze class and overload the << operator to print the maze.
Original Maze:
1111111111
1m01110111
1001001111
1111100111
1111000111
1000101011
1111110001
1111010111
10011111e1
1111111111Trapped -- No Way Out!
2 prog2b.cpp
The
following is an excerpt from Frank Stockton's famous short story "The Lady
or the Tiger?"
In the very olden time there lived a
semi-barbaric king…When
a subject was accused of a crime of sufficient importance to interest the king,
public notice was given that on an appointed day the fate of the accused person
would be decided in the king's arena… Directly opposite [the accused
subject], were two doors, exactly alike and side-by-side. It was the duty and
the privilege of the person on trial to walk directly to these doors and open
one of them. He could open either door he pleased… If he opened the one, there
came out of it a hungry tiger, the fiercest and most cruel that could be
procured, which immediately sprang upon him and tore him to pieces as a
punishment for his guilt... But, if the accused person opened the other door,
there came forth from it a lady, the most suitable to his years and station that
his majesty could select among his fair subjects, and to this lady he was
immediately married, as a reward of his innocence…This was the king's
semi-barbaric method of administering justice. Its perfect fairness is obvious.
The criminal could not know out of which door would come the lady; he opened
either he pleased, without having the slightest idea whether, in the next
instant, he was to be devoured or married.
If you read the story, the ending may surprise you.
In the
Hollywood version of
The
King's New Trial House
The network in the next figure is a second view of the house. Each numbered circle (vertex) represents a room and each line (edge) that joins two vertices is a door between rooms.
The Trial House , displayed as a network
A
blindfolded prisoner is led into the house and abandoned in one of the rooms,
where his blindfold is removed. In
another room the lady waits, and in a third room the tiger snarls.
Unable to hear the cheers and jeers of curious spectators, the prisoner
wanders through the house, from room to room to room, until he finds either the
lady who leads him to marital bliss or the tiger that… well you know.
If you examine the network in the previous figure, you will see that every room
is accessible from every other room. So
if the prisoner systematically moves through the house, he will eventually come
upon either the lady or the tiger.
Write an application that simulates the movements of
the prisoner through the rooms of the house.
The application should report the rooms that the prisoner visits, in the
order that he visits them, as well as the final outcome - the lady or the tiger.
Before can can implement an algorithm that moves the prisoner through the house,you must decide on an internal representation of the house. On paper, the above figures visually capture the important features of the house – the number and location of rooms and the location of each doorway. But these diagrams cannot serve as data for an eye-less program. So, represent the house as a two-dimensional array, rooms. The rows and columns of rooms are indexed by the room numbers. If i and j are two room numbers then
rooms(i,j) = 1 if there is a door between room i and room j
rooms(i,j) = 0 if there is no door between room i and room j
The next picture shows a small network of rooms and the corresponding array representation.
A
small network and its array representation
The prisoner "visits" rooms, until he discovers the lady or the tiger. To ensure that the program eventually terminates, the prisoner never re-visits the same room. Here is one method that systematically moves the prisoner through the house until the lady or the tiger is discovered. Notice that he never checks a room twice. When the prisoner can go no farther in a room he backtracks to the previous room and chooses a door that has not previously been selected. Use a stack for backtracking. Each time the prisoner enters a room, push the room number on the stack.
Here
is an algorithm:
Mark
the initial room as visited.
Push the initial room onto a stack of room numbers.
while both the lady and the tiger
are undiscovered
{
if there is an unvisited room r adjacent to
room on top of the stack
Visit r; mark r as visited.
if
the lady or tiger is in r,
the
search is over
otherwise
push r onto the stack, i.e., move the prisoner to room r.
else if there is no unvisited room adjacent to the room on top of the stack
backtrack to
the previous room so that previous
room visited is now on top of the stack
}
report the results
Read the
" house map" into an array from a file called rooms.txt.
Output should go to the screen
When the prisoner selects the next room....choose that room at random from the choices
Running
the game twice, with the same input data produces the following different
results. Because, the "next
room" is selected randomly,
the outcomes differ.
|
Output 1 |
Output 2 |
|
What is the starting room?: 0 Where is the tiger? 19 Where is the lady? 21 Starting in room 0 the prisoner visits rooms: 1 3 5 6 14 18 19 He found the tiger in room 19 |
What is the starting room?: 0 Where is the tiger? 19 Where is the lady? 21 Starting in room 0 the prisoner visits rooms: 1 3 5 6 7 4 8 13 9 11 15 16 12 17 20 21 He found the lady in room 21 |
|
|
|
Here is what happens in
each of the two runs use the graph to trace through the prisoner's route each
time so you can see the backtracking.
0 1 3 5 6 (backtrack to 5) 14 18 19
-------------------------------------------
0 2 1 3 5 6 (backtrack to 5) 7 4 8 13 9 11 15 16 (backtrack to 15) (backtrack to 11) 12 17 20 21
Call this program Prog2b.cpp
3. prog2c.cpp Do problem 3 on page 212 of the text. Use a recursive divide and conquer algorithm. Read the data from a file.
This is a short program. Don't complicate it. Think first!!!
