2015 Fall Computer Science I Program #4: Get Out of This Maze!!!
Please consult Webcourse for the due date/time
Queues have many uses. One use of a queue is that it can be used to help find the fastest way out
of a maze! The queue is an integral part of a search that is more generally called a Breadth First
Search. The idea is as follows. Given a starting point in a maze, travel to all places adjacent to it
and mark these as being 1 step away from the start point. Then, for each of these spots that are 1
step away, try travelling to all adjacent spots that are not yet visited. Mark these as 2 spots away.
Continue until one of the spots you mark is an exit! By hand, it’s quite easy to visually solve this
problem. In order to write a program to do it for a 2D array maze, you need a queue that keeps
track of each place you have reached that you haven’t yet tried to visit new places from. The
queue is necessary because to get shortest distances, you must process each possible location in
the order in which you arrived to them. In addition, as you travel, you should mark which places
you’ve reached so far, so that you don’t try to travel to them again. This second part is critical!
Without it, you’ll revisit some squares many, many times, resulting in a very slow algorithm.
Let’s run through an example by hand, showing what has to happen, visually in code, in both the
queue and the 2D array that is storing all shortest distances. We initialize any unvisited square to
-1 to indicate that it is in fact, unvisited. When we visit that square, we will update its value to
the shortest distance to travel there.
Consider the following maze:
~~~~~~~
~XXXXX~
~X-S-X~
~--X-X~
~~~~~~~
Let’s assume we can only move up, down, left and right from where we currently are. Let S
denote the starting square, let X denote an illegal square to move to, let ~ represent the outer
boundary to which we are trying to get to, and let – denote a square which is free to visit.
Our initial arrays and queue would look like this:
~~~~~~~
~XXXXX~
~X-S-X~
~--X-X~
~~~~~~~ -1
-1
-1
-1
-1 -1
-1
-1
-1
-1 -1
-1
-1
-1
-1 -1
-1
0
-1
-1 -1
-1
-1
-1
-1 -1
-1
-1
-1
-1 -1
-1
-1
-1
-1 Queue: (2,3) At this point, we dequeue the next item and try to go to all possible adjacent squares, which are
(2, 2) and (2, 4). We enqueue both of these into the queue, marking that the distance to both of
them is 0 + 1 = 1. It does not matter which order we enqueue these two items. (The 0 comes from
the distance to (2,3) the +1 is for the move left or right.) After this iteration, we have the
following: ~~~~~~~
~XXXXX~
~X-S-X~
~--X-X~
~~~~~~~ -1
-1
-1
-1
-1 -1
-1
-1
-1
-1 -1
-1
1
-1
-1 -1
-1
0
-1
-1 -1
-1
1
-1
-1 -1
-1
-1
-1
-1 -1
-1
-1
-1
-1 Queue: (2,2), (2,4) Next, we dequeue (2,2) and look for its unvisited neighbors (note that (2,3) is visited because in
the distance array, 0 is stored in that slot, not -1.) The only unvisited neighbor of (2, 2) is (3, 2),
so we update the distance to (3, 2) and enqueue it to get:
~~~~~~~
~XXXXX~
~X-S-X~
~--X-X~
~~~~~~~ -1
-1
-1
-1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 1 0 1 -1
-1 2 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1
-1
-1
-1 Queue: (2,4), (3,2) Next, we dequeue (2,4) and look for its unvisited neighbors (note that (2,3) is visited because in
the distance array, 0 is stored in that slot, not -1.) The only unvisited neighbor of (2, 4) is (3, 4),
so we update the distance to (3, 4) and enqueue it to get:
~~~~~~~
~XXXXX~
~X-S-X~
~--X-X~
~~~~~~~ -1
-1
-1
-1
-1 -1 -1 -1 -1
-1 -1 -1 -1
-1 1 0 1
-1 2 -1 2
-1 -1 -1 -1 -1
-1
-1
-1
-1 -1
-1
-1
-1
-1 Queue: (3,2), (3,4) Now, we dequeue (3,2) and look for its unvisited neighbors The only unvisited neighbors of (3,
2) are (3, 1), and (4, 2). We update the distance to both of these and enqueue to get:
~~~~~~~
~XXXXX~
~X-S-X~
~--X-X~
~~~~~~~ -1
-1
-1
-1
-1 -1 -1 -1 -1
-1 -1 -1 -1
-1 1 0 1
3 2 -1 2
-1 3 -1 -1 -1
-1
-1
-1
-1 -1
-1
-1
-1
-1 Queue: (3,2), (3,4) Theoretically, we could be smart enough to recognize that (4, 2) is on the boundary and that the
shortest way out is 3. In code though, most people end up waiting to stop the search until (4, 2) is
dequeued, so in this trace, we will continue from this point. Here is the current state:
~~~~~~~
~XXXXX~
~X-S-X~
~--X-X~
~~~~~~~ -1
-1
-1
-1
-1 -1 -1 -1 -1
-1 -1 -1 -1
-1 1 0 1
3 2 -1 2
-1 3 -1 -1 -1
-1
-1
-1
-1 -1
-1
-1
-1
-1 Queue: (3,4), (3,1), (4, 2) Now, we dequeue (3, 4) and get to this state, once we perform all necessary duties:
~~~~~~~
~XXXXX~
~X-S-X~
~--X-X~
~~~~~~~ -1
-1
-1
-1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 1 0 1 -1 -1
3 2 -1 2 -1 -1
-1 3 -1 3 -1 -1 Queue: (3,1), (4,2), (4,4) Next, we dequeue (3, 1):
~~~~~~~
~XXXXX~
~X-S-X~
~--X-X~
~~~~~~~ -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 1 0 1 -1 -1
4 3 2 -1 2 -1 -1
-1 4 3 -1 3 -1 -1 Queue:(4,2),(4,4),(3,0),(4,1) Finally, when we get here, we dequeue (4, 2) and realize that we’re out of the maze and return
our final answer of 3. Note: If you want, you can return this value right when this spot would
have been enqueued.
The Problem
Given a maze as described previously, determine whether or not there is a way to escape to the
boundary, and if so, what the shortest distance to escape the maze to any of the boundary
positions is. At each move, you may move up, down, left or right from your previous spot, so
long as the new spot isn’t forbidden.
The Input
The first line of the input file will contain a single positive integer, c (c ≤ 100), representing the
number of input cases. The input cases follow, one per line. The first line of each input case will
contain two positive integers, r(3 ≤ r ≤ 300), and c(3 ≤ c ≤ 300), representing the number of rows
and columns, respectively, in the maze. The following r lines will contain strings of exactly c
characters, describing the contents of that particular row using the symbols described above (~,
X, -, S). You are guaranteed that the first and last rows and first and last columns will only
contain the border character, ~. You are guaranteed that this character will not appear anywhere
else in the grid. Exactly one non border character will be an S, so there will always be exactly
one starting location. Finally, the rest of the squares will either be -, to indicate that that square
is valid to travel to, or X, to indicate that you may not travel to that square.
The Output
For each case, if it’s possible to reach the border of the maze, output the fewest number of steps
necessary to reach any border square. If it’s not possible, output -1. Sample Input
2
3 3
~~~
~S~
~~~
5 6
~~~~~~
~XXXX~
~XS-X~
~-XX-~
~~~~~~ Sample Output
1
-1 Specification Details
You must implement a queue of ordered pairs or integers to receive full credit on this
assignment. A significant portion of the grade will NOT come from execution, but rather the
implementation of an appropriate struct to store a queue AND the implementation of the Breadth
First Search algorithm described in this problem write-up.
Deliverables
Please turn in a single source file, maze.c, with your solution to this problem via Webcourses
before the due date/time for the assignment. Make sure that your program reads form standard in
and outputs to standard out, as previously shown in lab.