4 人解决，8 人已尝试。
5 份提交通过，共有 47 份提交。
8.4 EMB 奖励。
2306. Navigating the Reefs
单点时限: 2.0 sec
内存限制: 256 MB
Captain Jack Sparrow is planning a cruise around the treacherous coral reefs of the Caribbean. He knows the locations of the reefs, and he has his route planned out. His route starts at coordinate (0, 0). The route consists of a number of straight-line segments, each of which is given by one of the four compass directions (N, E, S, W) and a distance in miles. For example, [N 3] means that he travels north for 3 miles (placing him at (0, 3)). Suppose that the next day the segment is [E 5], which means that he then continues east for 5 miles (placing him now at location (5, 3)). If there is a reef at location (5, 3), then his ship will collide with it and sink. (And poor Jack and his crew pay a visit to Davy Jones’ locker. Arrrgh!)
There is an additional catch, however. At the end of each segment (including the last one) the ship may drift one mile in any one of the four compass directions, or it may not drift at all. The direction of the drift is entirely unknown, and it may be different for each segment. Jack must determine whether the voyage is free from any possibility of collision, no matter what combination of drifts occur. Let us consider the previous example, [N 3], [E 5]. Suppose that there is also a reef at location (3, 4). This voyage is not safe, because after the first segment (which ended at (0, 3), the ship might drift one mile to the north (placing it at (0, 4)), after which the next east segment will lead it straight into the reef. (And again, Arrrgh!)
Your job is to write a function that Jack can use to determine whether the voyage is safe from reefs. The function will be given the reef locations, followed by a series of segments. All quantities are integers. If there is any possibility of collision, your function will output the index of the first reef that could be hit. If the route is safe, then your function will return -1.
输入格式
We have provided a main program for you that handles all the input and output. The quantities it inputs are listed below and are stored as global variables. The variable oceanLimit indicates the limits of the entire ocean. An input of 20, for example, means that the ocean area in which Jack’s ship can travel is limited to -20 ≤ x ≤ +20 and -20 ≤ y ≤ +20. You may assume that Jack’s voyage, even allowing for drifting, will never extend outside these limits. The variables nReefs and nSegs give the number of reefs and number of segments. The arrays reefX[ ] and reefY[ ] contain the x- and y-coordinates of the reefs, respectively. The array segDirec[ ] contains the direction of each segment, as a single character, and the array segLength[ ] contains the length of each segment in miles.
输出格式
All you need to do is to provide the body for the function checkVoyage(), which determines whether the voyage is safe from any possible collision. If so, it returns -1. If not, it returns the index r, where 0 ≤ r ≤ (nReefs - 1), and r is the first reef that may cause a collision. The prototype is private static int checkVoyage();
Consider the example below, in which the segments are [N 3], [E 2], [S 5], [S 2]. On the left we show the voyage without drifting. On the right we show the combination of drifts after each segment that result in a collision with reef 2. (Note that the ocean limit is ±20, rather than ±6 as drawn in the figure.)
样例
Input
20 5 -1 5 5 2 -1 -5 -2 -2 -1 2 4 N 3 E 2 S 5 S 2
Output
Ocean limits: -20..20 Reefs: (-1,5) (5,2) (-1,-5) (-2,-2) (-1,2) Segments: [N 3] [E 2] [S 5] [S 2] Collision with reef 2 at (-1, -5) Hint: Output "No collision" if no collision
题目标签