PROBLEM STATEMENT
Cat Taro has a triangle board divided into hexagonal cells. The board contains N rows numbered 0
through N-1 from top to bottom, where the i-th row contains (i+1) hexagonal cells numbered (i,0)
through (i,i) from left to right. For example, if N = 4, the board looks like the picture below.
Each cell contains a token. Rabbit Hanako locked some cells so that tokens in those cells can't be
moved. You are given a vector board containing exactly N elements. For all i between 0
and N-1, inclusive, the i-th element of board will contain exactly (i+1) characters. If the j-th
character of the i-th element of board is 'X', the cell (i,j) is locked. If the j-th character of
the i-th element of board is '.', the cell (i,j) is unlocked.
Cat Taro can perform the following operation an arbitrary number of times: Choose three distinct
unlocked cells A, B and C. These three cells must have a common vertex. Move the token in cell A
to cell B, the token in cell B to cell C and the token in cell C to cell A.
Return the number of different board states he can achieve by performing operations as described
above, modulo 1,000,000,007. Two states are different if there exists at least one token that is
placed in a different cell in one state than it is in the other state.
DEFINITION
Class:HexagonPuzzle
Method:theCount
Parameters:vector
Returns:int
Method signature:int theCount(vector board)
CONSTRAINTS
-board will contain between 1 and 50 elements, inclusive.
-The i-th (0-indexed) element of board will contain exactly i+1 characters.
-Each character in board will be '.' or 'X'.
EXAMPLES
0)
{".",
".X",
"X..",
".X.X"}
Returns: 3
Example from the problem statement.
He can achieve the following three board states.
??
1)
{"X"}
Returns: 1
Taro can't perform any operation.
2)
{".",
"..",
"...",
".X.."}
Returns: 20160
3)
{".",
"..",
"XXX",
"..X.",
".X..X",
"XXXX..",
"..X.X.X",
"..X.XX.."}
Returns: 108
4)
{".",
"..",
"...",
"....",
".....",
"......",
".......",
"........"}
Returns: 261547992
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)2010, TopCoder, Inc. All rights reserved.