EE 355 PA2
EE 355 PA2 ¨C A-maze-ing
1 Introduction
In this programming assignment you will write a program to read a given maze
configuration (provided as an ASCII text file) and then find the shortest path (in
terms of number of steps) from the source location to the finish.
This programming assignment should be performed INDIVIDUALLY. You may reuse portions of code from previous examples and labs provided in this class, but
any other copying of code is prohibited. We will use software tools that check all
students¡¯ code and known Internet sources to find hidden similarities.
2 What you will learn
After completing this programming assignment you will:
1. Use file streams to perform text file I/O
2. Perform dynamic memory allocation of arrays.
3. Understand 2D array index computation
4. Apply a Breadth-First-Search algorithm to find a shortest path through the maze
3 Background Information and Notes
Our goal is to find a shortest path through a given maze specified in a text file. The
first step is to read in a maze from a text file. We have defined the following format
of these files. The first line of the file contains two integer numbers indicating the
row and column size of the maze. The number of rows indicated will determine
how many lines of text follow (1 row per line). On each line will be one character
for each of the indicated number of columns followed by a newline character. The
characters can be a period (.) indicating a space in the maze, a ¡®#¡¯ sign indicating a
wall in the maze, an ¡®S¡¯ indicating the start location for your search, or an ¡®F¡¯ for the
desired finish location. We assume that WALLS are implicitly surrounding the
perimeter of the maze.
Sample Input File
4 4
..#.
..#S
F.#.
....
Character
. (period)
#
S
F
Last Revised: 2/11/2015
General File Format
rows cols
\n
...
\n
Meaning
Free space in the maze
Wall in the maze
Start location in the maze
Finish location in the maze
1
EE 355 PA2 - A-maze-ing
After reading in the maze, your search algorithm will attempt to find a shortest
path from the start cell to the finish. If successful, you will need to indicate this
path by filling in the character locations along the path with an asterisk, ¡®*¡¯ and
then write the resulting character (maze) array to an output text file. The output
text file for the maze given above should look as follows.
Output File
4 4
..#.
..#S
F*#*
.***
Breadth-First Search (BFS): A common computer search algorithm is known as
Breadth First Search. In any search algorithm we select a starting source location
and continue exploring successive, non-wall locations until we find our intended
destination/finish location or no more legal locations exist to be searched (i.e. no
path exists to the finish location). As we search we mark cells that we've explored
so that we don't explore them again. A BFS algorithm has the property that we
always explore ALL locations at a shorter distance from the start/source before
exploring any location at a longer distance from the start/source (i.e. all locations at
a distance of i are explored before any location at a distance of i+1 from the
source). This ensures a shortest path will be found.
File I/O: You will use an ifstream object discussed in class to read the maze data in
from the given file and an ofstream object to write your results to an output file.
Remember you can use the ifstream object like you do cin to read data into
variables (int or chars for this assignment). Also like cin, the ifstream object will
skip whitespace (newline characters in particular) so you can treat the input file
data as one contiguous set. Also by reading the number of rows and columns into
two integers initially, you can determine exactly how many subsequent characters
to read in and then just loop through reading one character at a time.
2-D Array Indexing: You will not know the size of the maze until run-time when the
maze file is specified. Thus we will need to dynamically allocate an array to hold
the maze data. In C/C++ it ends up being relatively difficult to use dynamic memory
allocation for a 2D array. Thus, we will allocate a 1-D array of NROWS*NCOLS
items. Though we cannot access the 1-D array with two indices directly (i.e.
maze[row][col] won¡¯t work if we only have a 1D array), we can ¡°artificially¡± use two
index values by computing the 1D index from the two index values. Since each row
has NCOLS items, we need to skip over NCOLS items for each row we want to move
down.
Thus, to access the item at row r, column c, we should access: maze[r*NCOLS + c].
If we are given a 1D index, idx, we can convert it to row/column indices by:
performing: r = idx / ____________; c= idx %______________;
2
Last Revised: 2/11/2015
EE 355 PA2 - A-maze-ing
4 Requirements
Your program shall meet the following requirements for features and approach:
1. Break your program into three files with the given structure:
File
Description / Function Definitions
main(int argc, char *argv[])
maze.cpp
? Accepts the input filename and output filename as
command line arguments
? Calls other functions
int maze_search(char *maze, int rows, int cols)
?
?
maze_io.h
maze_io.cpp
Performs the BFS search for a valid path, filling in the
path with ¡®*¡¯ characters if found
Returns 1/true if a valid path was found, 0/false if no
path was found and -1 if an error occurred during the
search. Possible errors include inability to find the start
(¡®S¡¯) cell or finish (¡®F¡¯) cell.
Prototypes for functions in maze_io.cpp
Functions:
char * read_maze(char *filename, int *rows, int *cols );
?
Reads the maze from the given filename, allocates an
array for the maze and returns it. The rows and cols
arguments should point to variables that can be filled in
with the dimensions of the maze read in from the file.
void print_maze(char *maze, int rows, int cols);
?
Prints the maze to the screen in a two dimensional
format
void write_maze(char *filename, char *maze, int rows, int cols);
?
Write the contents of the maze array to the given
filename in the correct text file format.
2. A valid path consists of steps north, west, south, and east but no diagonals.
3. Dynamically allocate a 1D array to hold the maze data. Use the ¡°artificial¡± 2D
indexing (r*NCOLS + c) discussed in the Background section to access this
array and any other array that mimics a 2D array (i.e. the predecessor array
discussed below).
4. Your BFS search will need to dynamically allocate an array for your BFS
array/queue of locations to be explored.
A list/queue is a data structure known as a FIFO (First-In, First-Out) and has
the property that items go in the back (or tail) but are removed from the
front (head). It acts like a list where we right items at the bottom and cross
Last Revised: 2/11/2015
3
EE 355 PA2 - A-maze-ing
them off as we do them from the top. It serves to help us remember what
we have to do (until it is time to actually process it) and in what order the
work arrived.
Array representing BFS lists/queue/FIFO:
Head
Tail
0
1
2
3
item
item
-
4
-
5
-
6
-
To implement this behavior let us allocate a large array (NROWS * NCOLS
which is large enough to hold all items if we needed). We will also maintain
two integer indices: head (the index of the front item) and tail (the index of
the back item). Both should start at 0. When an item is added, it should be
placed at the index specified by tail (i.e. 0 for the first item added) and then
the tail index should be incremented (i.e. to 1). Another addition to the
queue would cause the same behavior (placed at location specified by the
tail index and then the tail index incremented). When an item is to be
removed and processed, we should always take it from the front (head)
index and then increment the head. Now, we must be careful not to try to
remove an item if the list is ¡°empty¡±. We would know this if the head and
tail index are ever equal. Thus, by checking that tail > head, we can safely
know that items exists in the queue.
As you start your BFS, place valid cells not previously found (already in the
queue or already taken out of the queue) into the queue. The general steps
a BFS are shown below. Take note of how the BFSQ (BFS array) are used as
well as the predecessor array which is explained below:
add start location to BFSQ
while BFSQ is not empty do
front ................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- what are my series ee bonds worth
- how much are my ee bonds worth
- ee bond calculator maturity value
- ee bonds calculator us treasury
- ee savings bond value chart
- ee savings bonds current value
- ee savings bonds value chart
- series ee bond redemption chart
- 1996 series ee bond value
- series ee savings bond calculator
- interest on series ee bonds
- when do series ee savings bonds mature