Problem Statement | |||||||||||||
| You are playing a video game that involves escaping from a dangerous area. Within the area there are DEADLY regions you can't enter, HARMFUL regions that take 1 life for every step you make in them, and NORMAL regions that don't affect you in any way. You will start from (0,0) and have to make it to (500,500) using only Up, Left, Right, and Down steps. The map will be given as a String[] deadly listing the DEADLY regions and a String[] harmful listing the HARMFUL regions. The elements in each of these parameters will be formatted as follows: Input format(quotes for clarity): "X1 Y1 X2 Y2" where (X1,Y1) is one corner of the region and (X2,Y2) is the other corner of the region The corners of the region are inclusive bounds (i.e. (4,1) and (2,2) include x-values between 4 and 2 inclusive and y-values between 1 and 2 inclusive). All unspecified regions are considered NORMAL. If regions overlap for a particular square, then whichever region is worst takes effect (e.g. DEADLY+HARMFUL = DEADLY, HARMFUL+NORMAL = HARMFUL, HARMFUL+HARMFUL = HARMFUL, DEADLY+NORMAL=DEADLY). Damage taken at each step occurs based on the destination square and not on the starting square (e.g. if the square (500,500) is HARMFUL you WILL take a point of damage stepping onto it; if the square (0,0) is HARMFUL you WON'T take a point of damage stepping off of it; this works analogously for DEADLY squares). Return the least amount of life you will have to lose in order to reach the destination. Return -1 if there is no path to the destination. Your character is not allowed to leave the map (i.e. have X or Y less than 0 or greater than 500). | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Notes | |||||||||||||
| - | If two harmful regions overlap, the area where they overlap is exactly the same as non-overlapping harmful regions (i.e. the effect is NOT cumulative, and the overlapping region still takes exactly 1 life) | ||||||||||||
Constraints | |||||||||||||
| - | deadly will contain between 0 and 50 elements inclusive | ||||||||||||
| - | harmful will contain between 0 and 50 elements inclusive | ||||||||||||
| - | Each element of deadly and harmful will be of the form (quotes for clarity): "X1 Y1 X2 Y2" where X1,Y1,X2, and Y2 are integers between 0 and 500 inclusive and contain no leading zeros | ||||||||||||
| - | Each element of deadly and harfmul will contain no leading, trailing or extra whitespace | ||||||||||||
Examples | |||||||||||||
| 0) | |||||||||||||
| |||||||||||||
| 1) | |||||||||||||
| |||||||||||||
| 2) | |||||||||||||
| |||||||||||||
| 3) | |||||||||||||
| |||||||||||||
| 4) | |||||||||||||
| |||||||||||||