JOIN
Get Time

   Problem Statement  

 Problem Statement for RectangleAvoidingColoring

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 String[] 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: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 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.

This problem was used for:
       Member Single Round Match 485 Round 1 - Division I, Level Two