PROBLEM STATEMENT
There is an N x M board divided into 1 x 1 cells. The rows of the board are numbered from 0 to
N-1, and the columns are numbered from 0 to M-1. The cell located in row r and column c has
coordinates (r, c).
In a coloring of the board, each cell on the board is colored white or black. A coloring is called
rectangle-avoiding if it is impossible to choose 4 distinct cells of the same color so that their
centers form a rectangle whose sides are parallel to the sides of the board. In other words, a
coloring is rectangle-avoiding if, for each a, b, c, and d with 0 <= a < b < N, 0 <= c < d < M,
there is at least one white cell and at least one black cell among the cells (a, c), (a, d), (b,
c) and (b, d).
You are given a vector board representing a board. The j-th character of the i-th element
of board represents cell (i, j), and it can be 'W', 'B' or '?'. Here, 'W' indicates a white cell,
'B' indicates a black cell and '?' indicates an uncolored cell. For each uncolored cell, you may
choose to color it either white or black. Return the number of different rectangle-avoiding
colorings that can be achieved. If it is impossible to achieve a rectangle-avoiding coloring,
return 0.
DEFINITION
Class:RectangleAvoidingColoring
Method:count
Parameters:vector
Returns:long long
Method signature:long long count(vector board)
NOTES
-Two colorings are different if there is a cell on the board that is colored white in one coloring
and black in the other coloring.
-The answer will always fit into a 64-bit signed integer data type.
CONSTRAINTS
-board will contain between 1 and 50 elements, inclusive.
-Each element of board will contain between 1 and 50 characters, inclusive.
-All elements of board will contain the same number of characters.
-Each character in each element of board will be 'W', 'B' or '?'.
EXAMPLES
0)
{"??",
"??"}
Returns: 14
Since each cell can be black or white, there are 2^4 = 16 ways to color this board. Of them, only
2 monochromatic colorings are not rectangle-avoiding, so the answer is 16 - 2 = 14.
1)
{"B?",
"?B"}
Returns: 3
It is the same board as in previous example, but colors for some cells are already predefined.
There are 4 ways to color the remaining cells and in one of them the board becomes completely
black. Therefore the answer is 4 - 1 = 3.
2)
{"WW",
"WW"}
Returns: 0
This board is already colored and the coloring is not rectangle-avoiding.
3)
{"??B??",
"W???W",
"??B??"}
Returns: 12
4)
{"??",
"W?",
"W?",
"?W",
"W?"}
Returns: 16
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.