Boats | Topcoder Archive

Problem Statement

A number of famous problems ask about various creatures trying to get across a river, with only one boat. One version of the problem goes something like this:

There is one boat, with a maximum capacity of maxWeight kilograms. There are a number of different creatures, each of whom has an enemies list and a weight. The creatures may coexist on either shore of the river without fighting, but if any creature is on a boat with any of his or her enemies, there will be trouble. Also, the boat may never carry a group of one or more creatures whose combined weight exceeds the maximum capacity.

Given that navigating the boat across the river requires at least one creature, and that the boat starts on the same side as all of the creatures, you are to return the minimum number of times the boat must go across the river before all the creatures can reach the other side. If it is impossible to get all of the creatures from one side to the other, return -1.

Each creature's enemy list and weight will be represented by corresponding elements of enemies and weights, respectively. Each element of enemies will be a space delimited list of indexes (starting from 0) corresponding to other creatures.

Definition

Class:: Boats
Method:: minCrossings
Parameters:: String[], int[], int
Returns:: int
Method signature:: int minCrossings(String[] enemies, int[] weights, int maxWeight)
(be sure your method is public)

Constraints

enemies and weights will contain the same number of elements.
enemies and weights will both contain between 1 and 16 elements, inclusive.
maxWeight will be between 1 and 1,000,000, inclusive.
Each element of weights will be between 1 and 1,000,000, inclusive.
Each element of enemies will be a single space delimited list (no leading or trailing spaces) of distinct integers between 0 and the length of enemies - 1 with no extra leading 0's.
No element of enemies will contain the same integer as its index (i.e. no one will be his or her own enemy).

Examples

```
{"1 3","0 2","1 3","0 2"}
```
```
{1,1,1,1}
```
```
10
```
```
Returns: 5
```
Creature 0 has two enemies: creature 1 and creature 3. Creature 1 has two enemies: creature 0 and creature 2. Creature 2 has two enemies: creature 1 and creature 3. Creature 3 has two enemies: creature 0 and creature 2. Thus the only two possible subsets of creatures that may cross the river together (aside from single creatures, which may always cross alone) are {0,2} and {1,3}
```
{"1 3","4 2","","0 1 4","3"}
```
```
{20,4,12,8,9}
```
```
30
```
```
Returns: 9
```
One way (out of many) to do this is as follows (assume that all animals start on side 1, and B denotes the boat): side 1 | side 2 -------------+---------- B 0 1 2 3 4 | 0 1 4 | B 2 3 B 0 1 2 4 | 3 0 1 | B 2 3 4 B 0 1 2 | 3 4 0 2 | B 1 3 4 B 0 2 3 | 1 4 0 | B 1 2 3 4 B 0 4 | 1 2 3 | B 0 1 2 3 4 Note that, aside from single creatures, the only legal sets of creatures that may be in the boat are: {0,4}, {2,3}, {2,4}.
```
{"1 3","4 2","","0 1 4","3"}
```
```
{20,4,12,8,9}
```
```
50
```
```
Returns: 7
```
This is the same as the last example, except that the maxWeight has been increased so that {0,2} and {0,2,4} are both legal subsets of creatures that may be in the boat.

{"","","","","","","","","","","","","","","",""}

{10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10}

Returns: 5

```
{"","","",""}
```
```
{1,1,1,10}
```
```
9
```
```
Returns: -1
```

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.