Escape
TCI '02 Semifinals 2 · 2002-11-22 · by brett1479
TCI '02 Semifinals 2 · 2002-11-22 · by brett1479 · Graph Theory, Search
Problem Statement
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).
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).
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)
{}
{}
Returns: 0
There are no DEADLY or HARMFUL regions.
1)
{"500 0 0 500"}
{"0 0 0 0"}
Returns: 1000
(0,0) is DEADLY but that doesn't affect our path since we never step onto it (only from it). The rest of the map is NORMAL.
2)
{"0 0 250 250","250 250 500 500"}
{"0 251 249 500","251 0 500 249"}
Returns: 1000
Just enough space to get around the DEADLY regions.
3)
{"0 0 250 250","250 250 500 500"}
{"0 250 250 500","250 0 500 250"}
Returns: -1
No way around the DEADLY regions.
4)
{}
{"500 500 500 500"}
Returns: -1
Submissions are judged against all 88 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Escape with a public method int lowest(vector<string> harmful, vector<string> deadly) · 88 test cases · 2 s / 256 MB per case