ExploringHoneycombs | Topcoder Archive

Problem Statement

A bee is exploring honeycombs with hexagonal cells. Each cell can have a maximum of 6 adjacent cells: two in the same column, two in a column to the left, and two in a column to the right. Cells with less than 6 adjacent cells are considered boundary cells.

Some cells are empty, some contain one portion of honey, and some are filled with wax. The bee cannot pass through wax-filled cells. When the bee passes through a honey-filled cell, it can collect the one portion of honey from that cell if it wants to. After a cell is harvested, it becomes empty. The bee initially flies to an empty or honey-filled boundary cell. It then walks from cell to adjacent cell collecting honey until it reaches an empty or honey-filled boundary cell. Finally, it flies away. The bee cannot fly between cells while it's collecting honey. Each walk from a cell to an adjacent cell counts as one move. The arrival and departure flights do not count as moves.

You are given a String[] cells representing a fragment of honeycombs. '.' characters represent free space (no cell), 'E' characters are empty cells, 'H' characters are honey-filled cells, 'W' characters are wax-filled cells. Columns of honeycomb cells correspond to columns of characters in cells. Element 0 of cells corresponds to the highest row of honeycombs. If we assign 0-based indices to columns, odd columns (1,3,...) will begin half-a-cell lower than the even columns (0,2,...) (see examples for further clarification).

Return the minimal number of moves required for the bee to arrive, collect exactly n portions of honey, and depart.

Definition

Class:: ExploringHoneycombs
Method:: minWay
Parameters:: String[], int
Returns:: int
Method signature:: int minWay(String[] cells, int n)
(be sure your method is public)

Notes

There are no cells outside the fragment of honeycombs represented with cells, so all border cells are boundary.
Cells that are adjacent to free space ('.') are boundary cells.

Constraints

n will be between 1 and 9, inclusive.
The number of 'H' characters in cells will be between n and 9, inclusive.
cells will contain between 1 and 50 elements, inclusive.
Each element of cells will contain between 1 and 50 characters, inclusive.
All elements of cells will contain the same number of characters.
Each character in cells will be '.', 'E', 'W' or 'H'.
The empty and honey-filled cells of the honeycombs will be connected, i.e., the bee will be able to walk from any such cell to any another cell.
There will be at least one boundary cell not filled with wax.

Examples

```
{".E.",
 "EHW",
 "EEE"}
```
```
1
```
```
Returns: 2
```
Honeycombs look like this. The bee needs one step to move from any empty border cell to the honey cell in the middle and one step to return.
```
{"HWWWW",
 "EHEHW",
 "WWWWW"}
```
```
1
```
```
Returns: 0
```
The bee can fly to the upper-left cell, collect the honey from it and depart without moving.
```
{"WWWWW",
 "HHHHH",
 "WWWWW"}
```
```
4
```
```
Returns: 4
```
The bee has to start at any end of the "tunnel", and when it collects 4 portions of honey, it will be better to pass the last cell with honey (not collecting it) than to return through the empty cells.

{".EEE.",
 "EHHHE",
 "EH.HE",
 "EEHEE",
 "..E.."}

Returns: 5

{"WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEHW",
 "WEWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWEW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WEWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWEW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WEWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWEW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WEWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWEW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WEWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWEW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WEWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWEW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WEWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWEW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WEWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWEW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WEWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWEW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WEWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWEW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WEWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWEW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WEWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW",
 "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWEW"}

Returns: 2302

```
{"....",
 ".H.H",
 "H.H."}
```
```
4
```
```
Returns: 3
```

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.