ForeignVisitors | Topcoder Archive

Problem Statement

You are helping some foreign visitors find their way around the city. Tomorrow, each of them wants to visit a muesum, a restaurant, and a gift shop. However, they don't want to walk any further than necessary. Your job is to suggest the specific locations each should visit so that they minimize their walking. Because this is a city, all travel is on a grid system, so the walking distance between any two points is the Manhattan distance, Abs(x1 - x2) + Abs(y1 - y2).

You have a list of locations. pointType[i], x[i] and y[i] describe the i-th location. Each element of pointType is one of "V" for visitor, "M" for museum, "R" for restaurant, or "G" for gift shop. Each visitor can visit the three points of interest in any order, and must return to their starting location after. Return the total minimum distance travelled by all visitors, if your choose their destinations optimally.

Definition

Class:: ForeignVisitors
Method:: minDistance
Parameters:: String[], int[], int[]
Returns:: int
Method signature:: int minDistance(String[] pointType, int[] x, int[] y)
(be sure your method is public)

Constraints

pointType will have between 4 and 50 elements, inclusive.
Each element of pointType will be one of "V", "M", "R", or "G".
The elements of pointType will contain at least one each of "V", "M", "R", and "G".
x and y will have the same number of elements as pointType.
Each element of x will be between 0 and 1000, inclusive.
Each element of y will be between 0 and 1000, inclusive.

Examples

```
{"V", "M", "R", "G"}
```
```
{0, 3, 2, 1}
```
```
{0, 0, 2, 1}
```
```
Returns: 10
```
If this visitor goes to M->R->G and then back, or the reverse, that is fastest. Visiting the restaurant first is also possible, but either way results in having to travel a distance of 12 instead of 10.
```
{"V", "M", "R", "G"}
```
```
{0, 0, 0, 0}
```
```
{0, 0, 0, 0}
```
```
Returns: 0
```
This visitor is lucky... everything he wants is right where he is already staying.
```
{"V", "M", "R", "G", "V"}
```
```
{0, 3, 2, 1, 0}
```
```
{0, 0, 2, 1, 0}
```
```
Returns: 20
```
Similar to the first example, but notice now there are two visitors. We add the together the distances each travels.
```
{"V", "M", "M", "R", "G"}
```
```
{0, 3, 2, 2, 1}
```
```
{0, 0, 0, 2, 1}
```
```
Returns: 8
```
This visitor can pick a closer museum than in the first example, and save some walking.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.