TopCoder problem "ExploringHoneycombs" used in TCHS SRM 34 (Division I Level Three)



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

0)
    
{".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.

1)
    
{"HWWWW",
 "EHEHW",
 "WWWWW"}
1
Returns: 0
The bee can fly to the upper-left cell, collect the honey from it and depart without moving.
2)
    
{"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.
3)
    
{".EEE.",
 "EHHHE",
 "EH.HE",
 "EEHEE",
 "..E.."}
6
Returns: 5
4)
    
{"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"}
1
Returns: 2302
5)
    
{"....",
 ".H.H",
 "H.H."}
4
Returns: 3

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7831

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10769&pm=7831

Writer:

Nickolas

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Graph Theory