Description
Checkpoint 1
Did you notice that the rules prevent certain moves from occurring? What are they in particular? If you
don’t get them right you will not be able to do the lab correctly. Confirm your understanding with one of
the lab TAs.
Now, write a simple recursive program (from scratch) that reads a starting location, (x, y) and returns the
total number of different paths back to the origin when the entire grid is “free”. Two paths are different if
there is at least one step on the path that is different even if most of the steps are the same. As a hint, when
x == 0 and y == 0 there is 1 path, when x == 2 and y == 1 there are 3 paths, and when x == 2 and
y == 2 there are 6 paths.
To complete this checkpoint show a TA your program to count all paths back to the origin.
Checkpoint 2
Please download the files:
http://www.cs.rpi.edu/academics/courses/spring17/ds/labs/08_recursion/grid1.txt
http://www.cs.rpi.edu/academics/courses/spring17/ds/labs/08_recursion/grid2.txt
http://www.cs.rpi.edu/academics/courses/spring17/ds/labs/08_recursion/start.cpp
Starting from the supplied program, start.cpp, write a program to count the number of paths when some
of the grid locations are blocked. When a location is blocked, no path can go through it.
Before writing your own code, compile and run start.cpp. Use the files grid1.txt and grid2.txt as input.
These have a sequence of blocked locations, ending with the point location (0, 0) (which isn’t blocked, but
signals the end of the input). The next location is the location for the initial (x, y). By changing this location
you will be able to test your program in different ways.
To complete this checkpoint show a TA your code to find and count legal (unblocked) paths.
Checkpoint 3
Modify your program from Checkpoint 2 so that it finds and outputs a legal path from the given (x, y)
location to the origin. If there is more than one path, it does not matter which it outputs. Did you notice
that all legal paths to the origin are the same length under the rules provided?
To complete this checkpoint and the entire lab, show a TA or programming mentor your modified
program.
