Programming Assignment Solution

Background




You are Brian! You have spent the entire night painting \ROMANES EUNT DOMUS" all over Jerusalem. There is just one spot left. Unfortunately, it’s far away, and your grammar is wrong, so if any of the guards catch you, they will correct you on the proper use of the vocative plural declension and imperative conjugation. This will exhaust poor Brian, who has been up all night.




Fortunately, Brian has the support of the Judean People’s Front (or was it the People’s Front of Judea?), who can encourage Brian and remove some of his exhaustion by inviting Brian to their conference on \Other than sanitization, medicine, education, and order, what have the Romans ever done for us?".







Description




Brian is at the top left of an N N grid, and needs to get to the bottom right in order to paint his message. To reach his destination as soon as possible, he’ll only move along the shortest way, i.e. moving rightward and downward. Along the way, Brian can encounter Roman guards marked as negative integers, where the magnitude is the amount of damage they deal. The positive integers are tiles that heal Brian that amount of HP, P are tiles that prevent Brian’s next damage, and D are tiles that double Brian’s next healing e ect. If Brian reaches 0 HP or less, he collapses and the mission fails, so prevent that!




No matter how many P tiles and D tiles Brian encounters, their e ects don’t stack. For example, if Brian walks on a D tile when he’s already in the state of \doubling next healing e ect", nothing happens. When Brian next encounters a healing tile, the healing will be doubled. Afterwards, Brian returns to a \normal" state. The same applies for P tiles.




What is the minimum amount of life Brian needs in order to complete his task?




Input Format




Read from standard input. The input is guaranteed to be well-formed, as described below:




The rst line contains an integer N. Next N lines describe the grid, each containing N strings




separated by space. For each string:




If the string is P, it indicates tiles that prevent Brian’s next damage.




If the string is D, it indicates tiles that double Brian’s next healing e ect. Otherwise, the string should actually be a non-zero integer x.




 
x 0: the tile will heal Brian x HP.




 
x < 0: guard on the tile will deal jxj damage to Brian.













Page 1 of 2
USC CSCI 270 Programming Assignment (Fall 2018)
2










Output Format




Output one integer to standard output: the minimum life Brian needs to complete his task.




Sample




Input 1
Input 2
Input 3
Input 4








3
4
5
5
2 -1 -13
3PD10
5-67-89
-1 -1 -1 -1 -1
-2 -30 20
-5 -6 -2 -100
-67-89-10
D1234
15 -13 -1
1 -4 -5 -24
7-89-1011
-1-2-312


-3468
-8 9 -10 11 -12
510-112




9 -10 11 -12 13
10 5 50 -1 -300








Output 1
Output 2
Output 3
Output 4








1
2
5
210











Constraints




For all test cases, 2 N 100, no guard deals more than 1000 damage and no tile heals more than 1000 HP.




The table below shows types of tiles each test case includes.




Test case No.
Guards
Healing tiles
P tiles
D tiles










1-5
No
Yes
No
No










6-25
Yes
No
No
No










26-40
Yes
Yes
No
No










41-50
Yes
Yes
Yes
Yes













Solving easy test cases rst may help you work out other test cases; If you cannot solve all of them, try to solve as many as possible.




Submission Format




You can use C, C++, Python, or Java in this assignment, so long as you submit a single le containing the source code of your solution. grid.cpp contains the skeleton code for C++ solution. However, if you decide to use C, Python, or Java, please con rm that your program meets all the requirements and notify the grader the way to execute your program in comments of your code.




Grading




The full score of this assignment is 100, 2 points for each test case you pass.




You pass a test case if and only if your output is correct and your program terminates within 1 second with return value 0.












Page 2 of 2