Requirements
You must implement the function in finalproject.cpp, which solves the problem given. The
function is called solve, returns an unsigned integer, and takes as a parameter a 2D grid of
std::string. You are guaranteed that this grid is a square, with dimensions N by N, for some
integer N in the range [2, 100].
What is the problem? You are walking along a grid, starting at the top-left element (0,0). Your
goal is to get to the bottom-right corner, element (N-1, N-1). Every time you move, you may
move either right one or down one. You may not move up, nor left, nor may you move more
than one spot at once. You may not stand still at any iteration.
You begin with some positive integer number of hit points.
Every square of the grid has one of four types of marking.
● A string consisting of a positive integer x. Walking into this square increases your health
by the given value. This will never be a value higher than 1000.
● A string consisting of a negative integer x. Walking into this square decreases your
health by the absolute value. For example, if the string is “-5” then you lose 5 HP by
walking into that square.
● The string “P”. Your hit points don’t change upon walking into this square, but the next
time you enter a square that decreases your health, its effect is cancelled instead. The
effect of this does not stack: if you walk through two such squares and then two squares
with negative integers, you take damage from the second one.
● The string “D”. Your hit points don’t change upon walking into this square, but the next
time you enter a square that increases your health, its effect is doubled. The effect of
this does not stack: if you walk through two such squares and then two squares with
positive integers, the second one only heals the stated value.
It is possible to be under the influence of a “P” effect and a “D” effect at the same time. If you
are under the effect of both, and you walk into a square the increases your health, the effect is
doubled (use of the “D” effect), and you are still under the influence of the “P” effect.
The return value of the function is an unsigned integer representing the answer to the following
question: what is the fewest hit points you could begin with, such that you can walk from the
top-left to the bottom-right corner while never having fewer than one HP?
For this project, you have a few requirements:
● You must implement the function in finalproject.cpp. You are welcome to introduce
helper functions as well if you so choose. If you use additional files, remember that the
gather script will only gather files ending in .hpp or .cpp.
● Each test case must run in under ten seconds1 on a reasonably modern computer. Test
cases that take longer than this to run may be deemed to be incorrect. Note that this
means you may need to think a little about efficiency in your program. It also imposes a
restriction on me; in this case, the largest input grid is 100 x 100. For an N by N grid, it
is possible to solve the problem in O(N2).
● You may assume all inputs are valid
You may use standard libraries as appropriate, unless there is one that makes solving this
problem trivial. I am unaware of any such part of the library
You are explicitly permitted to use C++ standard library container classes (std::vector, std::set,
etc). You are welcome to ask anything you want about these libraries, or to look up material
about them online. Information about how to use an explicitly-permitted library may always be
shared among classmates, but refrain from telling one another how you solved a problem in the
assignment with them. For example, answering “how do I check if an element is in a std::set?”
is great and encouraged, while answering “what did you use std::set for in your project?” is not.
A good reference for the STL container classes (such as those listed above, including std::map)
is http://www.cplusplus.com/reference/map/map/ .
Remember that the purpose of this project isn’t to find a program that solves this problem, but
rather to code it yourself and to figure out the algorithm you need for yourself. Submitting work
that isn’t yours (for any reason) is a decidedly bad idea. If I find that you submitted code you
found online, or that you shared a solution with a fellow student, your grade will be worse than if
you hadn’t turned in this project at all. Similarly, do not post your solution online -- you can get
in trouble if this assignment is given in a future quarter and a student submits your work.
1 Technically, I use processor minutes for this, so (a) if I have something else running, it doesn’t count
against you when it’s on the processor, and (b) someone cannot get around this by spinning up extra
threads. You can use timeout 10s ./run gtest --gtest_filter=SampleTests.Sample1 to
test that particular test case, with a timeout of 10 seconds, on your own machine if you want.
I also run test cases when I don’t have other things running though.