PenLift
SRM 144 · 2003-04-30 · by LunaticFringe
Problem Statement
NOTE: There are images in the examples section of this problem statement that help describe the problem. Please view the problem statement in the HTML window to view them.
Given a picture composed entirely of horizontal and vertical line segments, calculate the minimum number of times you must lift your pen to trace every line segment in the picture exactly n times.
Each line segment will be of the form "<x1> <y1> <x2> <y2>" (quotes for clarity), representing a segment from (x1,y1) to (x2,y2). Segments may cross each other. Segments may also overlap, in which case you should count the overlapping region as appearing in the drawing only once. For example, say the drawing were composed of two lines: one from (6,4) to (9,4), and one from (8,4) to (14,4). Even though they overlap from (8,4) to (9,4), you should treat the drawing as if it were a single line from (6,4) to (14,4). You would not need to lift your pen at all to trace this drawing.
Notes
- The pen starts on the paper at a location of your choice. This initial placement does not count toward the number of times that the pen needs to be lifted.
Constraints
- segments will contain between 1 and 50 elements, inclusive.
- Each element of segments will contain between 7 and 50 characters, inclusive.
- Each element of segments will be in the format "
_ _ _ " (quotes for clarity). The underscore character represents exactly one space. The string will have no leading or trailing spaces. , , , and will each be between -1000000 and 1000000, inclusive, with no unnecessary leading zeroes. - Each element of segments will represent a horizontal or vertical line segment. No line segment will reduce to a point.
- n will be between 1 and 1000000, inclusive.
{"0 0 0 1"}
1
Returns: 0
{"0 0 0 1","0 0 -1 0","0 0 1 0"}
1
Returns: 1
{"0 0 0 1","0 0 -1 0","0 0 1 0"}
2
Returns: 0
{"0 0 0 1","0 0 -1 0","0 0 1 0","0 0 0 1",
"0 2 0 3","0 2 -1 2","0 2 1 2","0 2 0 3"}
1
Returns: 3
{"0 0 0 1","0 1 1 1","0 1 10 1","5 1 5 2","5 1 5 10",
"5 10 10 10"}
1
Returns: 1
{"-10 0 10 0","0 -10 0 10"}
1
Returns: 1
This picture looks like a plus sign centered at the origin. One way to trace this image is to start your pen at (-10,0), move right to (10,0), lift your pen and place it at (0,-10), and then move up to (0,10). There is no way to trace the picture without lifting your pen at all, so the method returns 1.
{"-10 0 0 0","0 0 10 0","0 -10 0 0","0 0 0 10"}
1
Returns: 1
The picture is the same as the previous example, except that it has been described with four line segments instead of two. Therefore, the method still returns 1.
{"-10 0 0 0","0 0 10 0","0 -10 0 0","0 0 0 10"}
4
Returns: 0
You are now required to trace each segment exactly 4 times. You can do so without lifting your pen at all. Start at (0,0). Move your pen left to (-10,0), then back right to (0,0), then left again to (-10,0), then right again to (0,0). You have now traced the first line segment 4 times. Repeat this process for the other three segments as well. Since no pen lifts were required, the method returns 0.
{"0 0 1 0", "2 0 4 0", "5 0 8 0", "9 0 13 0",
"0 1 1 1", "2 1 4 1", "5 1 8 1", "9 1 13 1",
"0 0 0 1", "1 0 1 1", "2 0 2 1", "3 0 3 1",
"4 0 4 1", "5 0 5 1", "6 0 6 1", "7 0 7 1",
"8 0 8 1", "9 0 9 1", "10 0 10 1", "11 0 11 1",
"12 0 12 1", "13 0 13 1"}
1
Returns: 6
The picture looks like this: To trace the picture using the minimum number of pen lifts, refer to the following diagram: Start by placing your pen at the yellow dot. Trace the yellow square. Now lift your pen and place it on the red dot. Move downward, tracing the vertical line segment, and then around the perimeter of the red rectangle. Lift your pen again and place it on the green dot. Trace the green lines using the same method as you did for the red lines. Lift your pen a third time, placing it on the magenta dot. Trace the magenta lines in a similar fashion. You will need to lift your pen three more times to trace each of the leftover white segments, for a grand total of 6 pen lifts.
{"-2 6 -2 1", "2 6 2 1", "6 -2 1 -2", "6 2 1 2",
"-2 5 -2 -1", "2 5 2 -1", "5 -2 -1 -2", "5 2 -1 2",
"-2 1 -2 -5", "2 1 2 -5", "1 -2 -5 -2", "1 2 -5 2",
"-2 -1 -2 -6","2 -1 2 -6","-1 -2 -6 -2","-1 2 -6 2"}
5
Returns: 3
This is an example of overlap. Once all the segments are drawn, the picture looks like this: You would need to lift your pen 3 times to trace every segment in this drawing exactly 5 times.
Submissions are judged against all 85 archived test cases, of which 10 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PenLift with a public method int numTimes(vector<string> segments, int n) · 85 test cases · 2 s / 256 MB per case