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 N1, and the columns are numbered from 0 to M1. 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 rectangleavoiding 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 rectangleavoiding 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 String[] board representing a board. The jth character of the ith 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 rectangleavoiding colorings that can be achieved. If it is impossible to achieve a rectangleavoiding coloring, return 0.   Definition   Class:  RectangleAvoidingColoring  Method:  count  Parameters:  String[]  Returns:  long  Method signature:  long count(String[] board)  (be sure your method is public) 
    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 64bit 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 rectangleavoiding, so the answer is 16  2 = 14. 

 1)     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)     Returns: 0  This board is already colored and the coloring is not rectangleavoiding. 

 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.
