EECS 281 – Winter 2021
Project 1:
Rescue the Countess
Due Tuesday, February 9, 11:59 PM
Overview
“It’s a-me, Marco!”Marco of the Fungus Province has just received news that Louser has taken
Countess Cherry captive in his dark, maze-like castle. With his twin brother, Luigino, Marco has
traveled many miles to reach the castle, dodging flying shells and jumping on angry
mushrooms. Now that he has entered the castle, he needs your help to rescue the Countess.
Using C++, you must implement some basic path finding algorithms to guide Marco to the
Countess and foil Louser’s evil plans!
Castle Layout
You must help Marco navigate through Louser’s castle. The castle contains up to 10 rooms,
with warp pipes to travel between them. The rooms are all squares of the same size (NxN).
Your program will be given a map or description of the castle that uses the following symbols:
● ‘.’ walkable room space
● ‘#’ walls (which cannot be walked on or through)
● ‘!’ one of Louser’s minions (which cannot be walked on or through)
● A digit ‘0’ to ‘9’ which indicates a warp pipe traveling to the same spot in the room
with the corresponding number
● ‘S’ Marco’s starting location
● ‘C’ location of Countess Cherry
You can assume, for the files that we give you, that there is exactly one location for Countess
Cherry and exactly one starting point for Marco. You still might want to verify this, just in case
an input file that you create breaks this rule.
Because you have a copy of the castle map, your task is to plan a path for Marco from the
starting position (‘S’) to the Countess (‘C’) that does not pass through any walls (‘#’) or
minions (‘!’). Marco can walk next to the minions, but cannot walk on top of them. Marco
doesn’t have time to get in a fight today!
Rooms are to be treated as if they are surrounded by walls; you are to treat both walls and room
edges as impassable terrain.
Marco can discover new locations north, east, south or west from any room space (‘.’) as well
Version 1-20-21
© 2021 Regents of the University of Michigan
1
as the starting location; no discoveries may be made diagonally. Your path planning
program must check that it does not move Marco off of the map, onto walls (‘#’), or onto
minions (‘!’).
In addition, when Marco steps onto a warp pipe (digits 0-9), he will only be able to discover the
location in the same row and column of the room corresponding to the warp pipe’s number. If
Marco steps on a warp pipe with digit, d, at row and column (r, c), in any room, then he’ll be
able to discover (r, c) in the room d. It is possible for this to continue from warp pipe to warp
pipe, if there are multiple rooms with warp pipes in the same location.
If room d doesn’t exist, no new location can be discovered. You’ll need to check for this. For
example, a castle with 2 rooms might have a pipe labelled 5, but room 5 does not exist, so
Marco won’t use this pipe.
Input file format (The Castle Map)
The program gets its description of the castle from a file that will be read from standard input
(cin). This input file is a simple text file specifying the layout of the castle. We require that you
make your program compatible with two input modes: map (M) and coordinate list (L).
The reason for having two input modes is that a large percentage of the runtime of your
program will be spent on reading input or writing output. Coordinate list mode exists so that we
can express very large maps with a minimal amount of input data; map input mode exists to
express maps whose input files are also easily human readable.
For both input modes (‘M’ and ‘L’):
● The first line of every input file will be a single character specifying the input mode, ‘M’ or
‘L’ (without quote marks). Unlike the output mode, which is given on the command
line (see below), this is part of the input file.
● The second line will be a single integer 1 ≤ R ≤ 10 indicating the number of rooms.
● The third line will be a single integer 1 ≤ N, indicating the size of each (and every) room
of the castle (each room is NxN in size and all rooms are the same size).
You can assume that N (and thus a row or a column index) will fit inside of an unsigned integer
variable (unsigned int or uint32_t),.
Comment lines begin with ‘//’ and they are allowed anywhere in the file after the first three
lines. When developing your test files, it is good practice to place a comment on line 4
describing the nature of the castle in the test file. Any castles with noteworthy characteristics for
testing purposes should be commented. The map file is also easier to read if there is a
comment line identifying the room number before the description of that room, but this is not
required. Comments are allowed in either input mode.
Version 1-20-21
© 2021 Regents of the University of Michigan
2
Additionally, there may be extra blank/empty lines at the end of any input file, your program
should ignore them. If you see a blank line in the file, you may assume that you have hit the
end.
Map input mode (M):
For this input mode, the file should contain a map of each room, in order. The rooms are
specified beginning with the lowest number room and working up. The lowest room is room 0;
that is to say, the rooms are 0-indexed.
An example map mode input file for a castle with two 4×4 rooms:
M
2
4
//sample M mode input file with two 4×4 rooms
//castle room 0
.C..
….
…S

.1

//castle room 1
….

…

.!..

…

BEWARE: DO NOT copy/paste from a PDF file! PDF files contain ligatures (invisible
characters) that may cause your code (or the autograder) to behave in unexpected ways.
Copy from the sample files that we give you, or retype it by hand.
Coordinate list input mode (L):
A coordinate list input file will contain a list of coordinates for at least all walls, minions, and
warp pipes in the rooms. Only one coordinate should appear on a given line. We do not require
that the coordinates appear in any particular order. A coordinate is specified in precisely the
following form: (room,row,col,character). The row and col positions range from 0 to
N-1, where N is the value specified at the top of the file. By default, all unspecified coordinates
within the rooms are of type ‘.’ (room space); however, it is still valid to redundantly specify
them.
Here is a valid L mode input file that describes rooms that are identical to those that the sample
M input file did:
Version 1-20-21
© 2021 Regents of the University of Michigan
3
L
2
4
//sample L mode input file, two 4×4 rooms
//castle room 0
(0,0,1,C)
(0,1,0,.)
(0,2,3,S)
(0,3,0,#)
(0,3,2,1)
(0,3,3,#)
//castle room 1
(1,1,0,#)
(1,2,1,!)
(1,3,0,#)
(1,3,3,.)
Invalid coordinates (for a castle with two 4×4 rooms):
(2,1,2,#) — Room 2 does not exist!
(1,4,2,.) — Row 4 does not exist!
(0,1,5,!) — Col 5 does not exist!
(0,0,1,F) — F is an invalid map character!
Routing schemes
You are to develop two routing schemes to help Marco get from the starting location to the
location of Countess Cherry:
● A queue-based routing scheme
● A stack-based routing scheme
Be sure to read the document on Canvas titled “Project 1 the STL and You”; it has some
excellent tips, plus a way to implement the two different routing schemes with a single search
container (the deque).
In the routing scheme use a search container (queue or stack) of locations within the castle.
First, initialize the algorithm by adding the start position ‘S’ to the search container. Then, loop
through the following steps:

1. Remove the next position from the search container.
2. If that position has a warp pipe, add the corresponding position that the pipe leads to,
   i.e., the same row/col position but with the specified room number. As noted below, only
   add this position if it has not been added to the search container before.
   Version 1-20-21
   © 2021 Regents of the University of Michigan
   4
3. If the position is not a warp pipe, then add all locations adjacent to the location you just
   removed that are available to move into (walkable room space, warp pipes, or the
   Countess’s location). Add any locations that you are allowed to move to from your
   present location in the following order: north, east, south, and west.
4. As you add any of these spaces (step 2 or 3) to the search container, check to see if any
   of them is the location of the Countess ‘C’; if so, stop searching for a path.
   If the search container becomes empty before you reach the Countess ‘C’, the search has
   failed and there is no path to rescue the Countess.
   Whenever you add a position to the search container, you have “discovered” it. Do not
   discover any position more than once. Remember that from a walkable room space tile ‘.’
   or your starting location ‘S’ you can only discover locations north, east, south, or west. Warp
   pipes are the only way of moving between rooms.
   When visiting a warp pipe, you still have to check that you haven’t added its target
   location to the data structure when you see it. This will help you prevent Marco from
   following warp pipe loops. Also, make sure that Marco doesn’t warp onto an enemy or into a
   solid wall! This is considered unhealthy.
   The program must run to completion within 35 seconds of total CPU time (user + system)

5. programs running for longer than this period will receive 0 points on that test case. In
   most cases 35 seconds is much more time than you should need; even if you finish before 35
   seconds, you may still receive no points because your solution is too slow. See the time
   manpage for more information (this can be done by entering“man time”to the command line).
   We may test your program on very large maps (up to several million locations). Be sure you are
   able to navigate to the Countess in large castle maps within 35 seconds. Smaller castle maps
   should run MUCH faster.
   Libraries and Restrictions
   Unless otherwise stated, you are allowed and encouraged to use all parts of the C++ STL and
   the other standard header files for this project. You are not allowed to use other libraries (eg:
   boost, pthread, etc). You are not allowed to use the shared_pointer or unique_pointer
   constructs from the memory include file (we want you to learn proper use of pointers yourself).
   You are not allowed to use the C++11 regular expressions library (it is not fully implemented in
   gcc 6.x) or the thread/atomics libraries (it spoils runtime measurements).
   Output file format
   The program will write its output to standard output (cout). Similar to input, we require that you
   implement two possible output formats. Unlike input, however, the output format will be
   specified through a command line option ‘–output’, or ‘-o’, which will be followed by an
   argument of M or L (M for map output and L for coordinate list output). See the section on
   Version 1-20-21
   © 2021 Regents of the University of Michigan
   5
   command line arguments below for more details.
   For both output formats, you will show the path you took from start to finish.
   If there is no valid solution, then, regardless of output mode, output
   No solution, N tiles discovered.
   (where N is the number of tiles discovered) followed by a newline.
   Map Output Mode (M):
   For this output mode, you should first print the starting location (see the example below). Then
   print the map of the castle rooms, replacing existing characters as needed to show the path you
   chose. Beginning at the starting location, overwrite the characters in the path with ‘n’, ‘e’,
   ‘s’, ‘w’, or ‘p’ to indicate which tile Marco moved to next. All pipes Marco used in the final
   path should be overwritten by ‘p’, regardless of what room they lead to or from. Do not
   overwrite the location of the Countess ‘C’ at the end of the path, but do overwrite the ‘S’ at
   the beginning. For all spaces that are not a part of the path, simply reprint the original room
   map space. You should only create comments to indicate the room numbers and format them
   as shown below, all other comments from the input files should be omitted.
   Thus, for the sample input file specified earlier, using the queue-based routing scheme and map
   (M) style output, you should produce the following output:
   Start in room 0, row 2, column 3
   //castle room 0
   .Cww
   …n
   …n

   .1

   //castle room 1
   ….

   …

   .!..

   …

   Using the same input file but with the stack-based routing scheme, you should produce the
   following output:
   Start in room 0, row 2, column 3
   //castle room 0
   eC..
   n…
   nwww
   Version 1-20-21
   © 2021 Regents of the University of Michigan
   6

   .1

   //castle room 1
   ….

   …

   .!..

   …

   We have highlighted the modifications to the output in red to call attention to them; do not
   attempt to color your output (this isn’t possible, as your output must be a plain text file).
   Coordinate List Output Mode (L):
   For this output mode, you should print only the coordinates that make up the path you traveled.
   You should print them in order, from (and including) the starting position to the ‘C’ (but you
   should not print the coordinate for ‘C’). The coordinates should be printed in the same format as
   they are specified in coordinate list input mode (room,row,col,character). The
   character of the coordinate should be ‘n’, ‘e’, ‘s’, ‘w’ or a ‘p’ to indicate spatially which
   tile is moved to next (as with map output, the ‘p’ indicates that a warp pipe was taken). You
   should discard all comments from the input file, but you should add one line, just before you list
   the coordinates of the path that says“Path taken:”.
   The following are examples of correct output format in (L) coordinate list mode that reflect the
   same solution as the Map output format above:
   For the queue solution:
   Path taken:
   (0,2,3,n)
   (0,1,3,n)
   (0,0,3,w)
   (0,0,2,w)
   For the stack solution:
   Path taken:
   (0,2,3,w)
   (0,2,2,w)
   (0,2,1,w)
   (0,2,0,n)
   (0,1,0,n)
   (0,0,0,e)
   There is only one acceptable solution per routing scheme for each castle. If no valid route
   exists, the program should print“No solution, N tiles discovered.”(followed by a
   newline), where N is the number of tiles you discovered while searching, and no other output, in
   Version 1-20-21
   © 2021 Regents of the University of Michigan
   7
   either output mode. If this occurs, do not output the starting location or“Path taken:”line.
   Be aware that input and output modes are independent of each other. Each test can use either
   input mode and either output mode. They may or may not be the same.
   Command line arguments
   Your program should take the following case-sensitive command line options (when we say a
   switch is “set”, it means that it appears on the command line when you call the program):
   ● –stack, -s: If this switch is set, use the stack-based routing scheme.
   ● –queue, -q: If this switch is set, use the queue-based routing scheme.
   ● –output (M|L), -o (M|L): Indicates the output file format by following the flag
   with an M (map format) or L (coordinate list format). If the –output option is not
   specified, default to map output format (M), if –output is specified on the command
   line, the argument (either M or L) to it is required. See the examples below regarding
   use.
   ● –help, -h: If this switch is set, the program should print a brief help message which
   describes what the program does and what each of the flags are. The program should
   then exit(0) or return 0 from main().
   When we say –stack, or -s, we mean that calling the program with –stack does the same
   thing as calling the program with -s. See getopt for how to do this.
   Legal command line arguments must include exactly one of –stack or –queue (or their
   respective short forms -s or -q). If none are specified or more than one is specified, the
   program should print an informative message to standard error (cerr) and call exit(1).
   Examples of legal command lines:
   ● ./superMarco –stack < infile > outfile
   ○ This will run the program using the stack algorithm and map output mode.
   ● ./superMarco –queue –output M < infile > outfile
   ○ This will run the program using the queue algorithm and map output mode.
   ● ./superMarco –stack –output L < infile > outfile
   ○ This will run the program using the stack algorithm and coordinate list output
   mode.
   Notice that we are using input and output redirection here. While we are reading our
   input from a file and sending our output to another file in this case, we are NOT using file
   streams! The < command redirects the file specified by the next command line argument to be
   the standard input (cin) for the program. The > command redirects the output of the program
   (things sent to cout) to be printed to the file specified by the next command line argument. The
   operating system makes calls to cin to read the input file and it makes calls to cout to write to
   Version 1-20-21
   © 2021 Regents of the University of Michigan
   8
   the output file. Come to office hours if this is confusing!
   Examples of illegal command lines:
   ● ./superMarco –queue -s < infile > outfile
   ○ Contradictory choice of routing
   ● ./superMarco < infile > outfile
   ○ You must specify either stack or queue
   Testing your solution
   It is extremely frustrating to turn in code that you are “certain” is functional and then receive
   half credit. We will be grading for correctness primarily by running your program on a number of
   test cases. If you have a single silly bug that causes most of the test cases to fail, you will get a
   very low score on that part of the project even though you completed 95% of the work. Most of
   your grade will come from correctness testing. Therefore, it is imperative that you test your
   code thoroughly. To help you do this we will require that you write and submit a suite of test
   files that thoroughly test your project.
   Your test files will be used to test a set of buggy solutions to the project. Part of your grade will
   be based on how many of the bugs are exposed by your test files. (We say a bug is exposed by
   a test file if the test file causes the buggy solution to produce different output from a correct
   solution.)
   Each test file should be an input file that describes a castle in either map (M) or coordinate list
   (L) format. Each test file should be named test-n-flags.txt where 1 ≤ n ≤ 15. The“flags”
   portion should include a combination of letters of flags to enable. Valid letters in the flags
   portion of the filename are:
   ● s: Run stack mode
   ● q: Run queue mode
   ● m: Produce map mode output
   ● l: Produce list mode output
   The flags that you specify as part of your test filename should allow us to produce a valid
   command line. For instance, don’t include both s and q, but include one of them; include m or l,
   but if you leave it off, we’ll run in map output mode. For example, a valid test file might be
   named test-1-sl.txt (stack mode, list output). Given this test file name, we would run your
   program with a command line similar to the following (the autograder will use a random
   combination of long and short options, such as –output instead of -o):
   ./superMarco -s –output L < test-1-sl.txt > test-1-output.txt
   Test files may have no more than 10 levels, and the size of a level may not exceed 8×8. You
   Version 1-20-21
   © 2021 Regents of the University of Michigan
   9
   may submit up to 15 test files (though it is possible to get full credit with fewer test files). The
   test cases the autograder runs on your solution are NOT limited to 10x8x8; your solution should
   not impose any size limits (as long as sufficient system memory is available).
   Errors you must check for
   A small portion of your grade will be based on error checking. You must check for the following
   errors:
   ● Input errors: illegal map characters (you should check in both M and L input modes).
   ● For L input mode, you must check that the room, row, and column numbers of each
   coordinate are all valid positions.
   ● More or less than one –stack or –queue or -s or -q on the command line. You
   may assume the command line will otherwise be correct (this also means that we will not
   give you characters other than ‘M’ or ‘L’ to –output).
   In all of these cases, print an informative error message to standard error (cerr) and call
   exit(1). In the starter files, look at the file named Error_messages.txt. If you output any
   one of those standard error messages when the input is actually valid, the autograder will repeat
   the error message back to you. This can be helpful when your program thinks that a valid input
   is invalid, because you can more easily figure out what went wrong.
   You do not need to check for any other errors.
   Assumptions you may make
   ● You may assume we will not put extra characters after the end of a line of the map or
   after a coordinate.
   ● You may assume that coordinates in coordinate list input mode will be in the format
   (room,row,col,character).
   ● You may assume that there will be exactly one start location ‘S’ and exactly one
   location of the Countess ‘C’ in the map.
   ● You may assume that we will not give you the same coordinate twice for the coordinate
   list input mode.
   ● You may assume the input mode line and the integer dimensions of the castle on lines
   two and three at the beginning of the input file will be by themselves, without
   interspersed comments, and that they will be correct.
   Submission to the Autograder
   Do all of your work (with all needed files, as well as test files) in some directory other than your
   home directory. This will be your “submit directory”. Before you turn in your code, be sure that:
   Version 1-20-21
   © 2021 Regents of the University of Michigan
   10
   ● Every source code and header file contains the following project identifier in a comment
   at the top of the file:
   ● // Project Identifier: B99292359FFD910ED13A7E6C7F9705B8742F0D79
   ● The Makefile must also have this identifier (in the first TODO block).
   ● DO NOT copy the above identifier from the PDF! It might contain hidden characters.
   Copy it from the Identifier.txt file from Canvas instead.
   ● You have deleted all .o files and your executable(s). Typing ‘make clean’ shall
   accomplish this.
   ● Your makefile is called Makefile. Typing ‘make -R -r’ builds your code without errors
   and generates an executable file called superMarco. The command line options -R
   and -r disable automatic build rules, which will not work on the autograder.
   ● Your Makefile specifies that you are compiling with the gcc optimization option -O3. This
   is extremely important for getting all of the performance points, as -O3 can often speed
   up code by an order of magnitude. You should also ensure that you are not submitting a
   Makefile to the autograder that compiles with the debug flag, -g, as this will slow your
   code down considerably. If your code“works”when you don’t compile with -O3 and
   breaks when you do, it means you have a bug in your code!
   ● Your test files are named test-n-flags.txt and no other project file names begin with test.
   Up to 15 test files may be submitted.
   ● The total size of your program and test files does not exceed 2MB.
   ● You don’t have any unnecessary files or other junk in your submit directory and your
   submit directory has no subdirectories.
   ● Your code compiles and runs correctly using the g++ compiler. This is available on the
   CAEN Linux systems (that you can access via login.engin.umich.edu). Even if
   everything seems to work on another operating system or with different versions of GCC,
   the course staff will not support anything other than GCC running on CAEN Linux. At the
   moment, the default version installed on CAEN is 4.8.5, however we want you to use
   version 6.2.0 (available on CAEN with a command and/or Makefile); this version is also
   installed on the autograder machines.
   Turn in all of the following files:
   ● All your .h, .hpp, and .cpp files for the project
   ● Your Makefile
   ● Your test files
   You must prepare a compressed tar archive (.tar.gz file) of all of your files to submit to the
   autograder. One way to do this is to have all of your files for submission (and nothing else) in
   one directory. Our Makefile provides the command make fullsubmit. Alternately you can
   go into this directory and run this command:
   dos2unix ; tar czf ./submit.tar.gz .cpp .h .hpp Makefile test*.txt
   This will prepare a suitable file in your working directory.
   Version 1-20-21
   © 2021 Regents of the University of Michigan
   11
   Submit your project files directly to either of the two autograders at:
   https://g281-1.eecs.umich.edu/ or https://g281-2.eecs.umich.edu/. When the autograders are
   turned on and accepting submissions, there will be an announcement on Piazza. The
   autograders are identical and your daily submission limit will be shared (and kept track of)
   between them. You may submit up to three times per calendar day (more during the Spring).
   For this purpose, days begin and end at midnight (Ann Arbor local time). We will count only
   your best submission for your grade. If you would instead like us to use your LAST
   submission, see the autograder FAQ page, or use this form. If you use an online revision
   control system, make sure that your projects and files are PRIVATE; many sites make
   them public by default! If someone searches and finds your code and uses it, this could
   trigger Honor Code proceedings for you.
   Please make sure that you read all messages shown at the top section of your
   autograder results! These messages will help explain some of the issues you are having
   (such as losing points for having a bad Makefile or using disallowed libraries).
   Grading

6. points — Your grade will be primarily based on the correctness of your algorithms. Your
   program must have correct and working stack and queue algorithms and support both types of
   input and output modes. Additionally: Part of your grade will be derived from the runtime
   performance of your algorithms. Fast running algorithms will receive all possible performance
   points. Slower running algorithms may receive only a portion of the performance points. The
   autograder machines keep track of the fastest run times (“click on View scoreboard”from the
   autograder project page). You may track your progress relative to other students and
   instructors there.
7. points — No memory leaks. Solutions that are proven to run (passing certain autograder test
   cases) will also be run through valgrind, to check for memory leaks at exit. This is something
   you should do yourself, to check for memory leaks as well as a number of other issues that
   valgrind can enumerate. Valgrind is available at the CAEN command prompt, and can also be
   downloaded to run on Linux-based personal environments.

8. points — Testing and Bug Finding (effectiveness at exposing buggy solutions with
   user-created test files).
   Grading will be done by the autograder.
   Version 1-20-21
   © 2021 Regents of the University of Michigan
   12
   Empirical efficiency
   We will check for empirical efficiency both by measuring the memory usage and running time of
   your code and by reading the code. We will focus on things such as whether you use
   unnecessary temporary variables, whether you copy data when a simple reference to it will do,
   and whether you use an O(n) algorithm or an O(n
   2
   ) algorithm.
   Coding style
   Although your project will not be graded on style, style is a very important part of programming
   and software development. Among other things, good coding style consists of the following:
   ● Clean organization and consistency throughout your overall program
   ● Proper partitioning of code into header and cpp files
   ● Descriptive variable names and proper use of C++ idioms
   ● Effective use of library (STL) code
   ● Omitting globals, unnecessary literals, or unused libraries
   ● Effective use of comments
   ● Reasonable formatting – e.g. an 80 column display
   ● Code reuse/no excessive copy-pasted code blocks
   ● Effective use of comments includes stating preconditions, invariants, and postconditions,
   explaining non-obvious code, and stating big-Oh complexity where appropriate
   It is extremely helpful to compile your code with the gcc options: -Wall -Wextra
   -pedantic -Wconversion. This will help you catch bugs in your code early by having the
   compiler point out when you write code that is either of poor style or might result in behavior that
   you did not intend.
   Hints and advice
   ● Design your data structures and work through algorithms on paper first. Draw pictures.
   Consider different possibilities before you start coding. If you’re having problems at the
   design stage, come to office hours. After you have done some design and have a
   general understanding of the assignment, re-read this document. Consult it often during
   your assignment’s development to ensure that all of your code is in compliance with the
   specification.
   ● Always think through your data structures and algorithms before you code them. It is
   important that you use efficient algorithms in this project and in this course, and coding
   before thinking often results in inefficient algorithms.
   ○ If you are considering linked lists, be sure to review the lecture slides or measure
   their performance against vectors first (theoretical complexities and actual
   runtime can tell different stories).
   Version 1-20-21
   © 2021 Regents of the University of Michigan
   13
   ● Only print the specified output to standard output.
   ● You may print whatever diagnostic information you wish to standard error (cerr).
   However, make sure it does not scale with the size of input, or your program may not
   complete within the time limit for large test cases.
   ● If the program does find a route, be sure to have main() return 0 (or call exit(0)). If
   the input is valid but no route exists, also have main() return 0.
   ● This is not an easy project. Start it immediately!
   Have fun coding!
   Version 1-20-21
   © 2021 Regents of the University of Michigan
   14
   Appendix A – More Sample Input/Output
   An additional simple test input that requires you to correctly use a pipe to solve it.
   Map Input:
   M
   2
   4
   //sample where using warp pipe is required
   //castle room 0
   .S..

   …

   ..!.

   .1.

   //castle room 1
   .C..
   .0..
   .!..

   ..

   List Input:
   L
   2
   4
   //sample where using warp pipe is required
   //castle room 0
   (0,0,1,S)
   (0,1,0,#)
   (0,2,2,!)
   (0,3,0,#)
   (0,3,2,1)
   //castle room 1
   (1,0,1,C)
   (1,1,1,0)
   (1,2,1,!)
   (1,3,0,#)
   (1,3,3,#)
   Version 1-20-21
   © 2021 Regents of the University of Michigan
   15
   Map Output (Queue):
   Start in room 0, row 0, column 1
   //castle room 0
   .s..

   s..

   .s!.

   ep.

   //castle room 1
   .Cw.
   .0n.
   .!n.

   .n

   List Output (Queue):
   Path taken:
   (0,0,1,s)
   (0,1,1,s)
   (0,2,1,s)
   (0,3,1,e)
   (0,3,2,p)
   (1,3,2,n)
   (1,2,2,n)
   (1,1,2,n)
   (1,0,2,w)
   Version 1-20-21
   © 2021 Regents of the University of Michigan
   16
   Map Output (Stack):
   Start in room 0, row 0, column 1
   //castle room 0
   .s..

   s..

   .s!.

   ep.

   //castle room 1
   .Cww
   .0.n
   .!en

   .n

   List Output (Stack):
   Path taken:
   (0,0,1,s)
   (0,1,1,s)
   (0,2,1,s)
   (0,3,1,e)
   (0,3,2,p)
   (1,3,2,n)
   (1,2,2,e)
   (1,2,3,n)
   (1,1,3,n)
   (1,0,3,w)
   (1,0,2,w)
   Version 1-20-21
   © 2021 Regents of the University of Michigan
   17
   An additional simple test input that requires you to correctly use a pipe to solve it.
   Map Input:
   M
   1
   3
   // A map with no solution
   //castle room 0
   S#C
   .#!
   …
   Output (same for all valid command line options):
   No solution, 5 tiles discovered.
   Appendix B – Test Case Legend
   Test case name: XnY
   X = L,M,S – “size” of input files
   n = Test case number, consecutive not informative
   Y = s,S – stack mode routing (map output, LIST OUTPUT)
   q,Q – queue mode routing (map output, LIST OUTPUT)
   Test case name: INVn
   n = Invalid test case number; see “Errors you must check for” section
   Test case name: SpecXYZ
   X (optional) = -P- – spec example w/ warp, <not specified> spec example no warp
   Y = L,M – List mode input, Map mode input
   Z = s,S – stack mode routing (map output, LIST OUTPUT)
   q,Q – queue mode routing (map output, LIST OUTPUT)
   When you start submitting test files to the autograder, it will tell you (in the section called
   “Scoring student test files”) how many bugs exist, the number needed to start earning points,
   and the number needed for full points. It will also tell you how many are needed to start earning
   an extra submit/day!
   Version 1-20-21
   © 2021 Regents of the University of Michigan