Connection Status:
Competition Arena > SimplePath

SimplePath

SRM 202 · 2004-07-07 · by dgoodman

SRM 202 · 2004-07-07 · by dgoodman · Geometry, Search
Class Name: SimplePath
Return Type: int
Method Name: trouble
Arg Types: (string, vector<int>)
Problem Statement

Problem Statement

A road has been laid out so that it consists of segments, each of which runs either North-South or East-West. We will say that one segment "touches" another segment if the two segments have a common point, other than the common point between two sequential segments in the path. We want to check the surveyor's data to make sure that it represents a simple path -- specifically one in which no two segments touch.

We are given a String direction and a int[] length giving the surveyor's data for each segment of the road. The i-th character of direction tells the direction ('N','E','S', or 'W') of the i-th segment, and the i-th element of length tells the length of that segment. Create a class SimplePath that contains a method trouble that is given direction and length and returns the zero-based index of the lowest-indexed segment that touches another segment. If no two segments touch, return -1.

Constraints

  • direction will contain between 1 and 50 characters inclusive.
  • length will contain the same number of elements as direction has characters.
  • Each character of direction will be an uppercase letter 'N', 'E', 'S', or 'W'.
  • Each element of length will be between 1 and 10,000 inclusive.
Examples
0)
"NWSEEN"
{5,5,3,2,5,2}
Returns: 0

The first segment goes north 5 units. The second then goes 5 west. The third segment goes 3 south. The fourth goes 2 east. The fifth segment continues east and touches (in fact intersects) the first segment. Return the zero-based index of the first segment.

1)
"NWWS"
{10,3,7,10}
Returns: -1

This road is a 10 x 10 x 10 U-shaped simple path.

2)
"NWES"
{2,2,1,2}
Returns: 1

Nothing touches the first segment, but the second segment touches the third segment. In fact, the third segment doubles back and covers half of the second segment. The zero-based index of the second segment is 1.

3)
"NWSE"
{100,100,100,100}
Returns: 0

This road forms a square, so the last segment touches the first segment and we return the index of the first segment.

4)
"NNNNNNNNNNNNNNNNNNNN"
{1,2,1,1,1,2,1,1,1,2,1,1,1,2,1,1,1,2,1,1}
Returns: -1

Submissions are judged against all 32 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SimplePath with a public method int trouble(string direction, vector<int> length) · 32 test cases · 2 s / 256 MB per case

Submitting as anonymous