TopCoder problem "DrawingBlackCrosses" used in SRM 466 (Division I Level Three)



Problem Statement

    Pavel likes puzzles. One of his favorite puzzles is DrawingBlackCrosses. In this puzzle, the player starts with a rectangular grid of cells, where each cell is either white or black, and at most 8 of the cells are black. The player's goal is to achieve the state where all of the cells in the grid are black. To achieve this goal, a sequence of moves must be performed. In each move, a single white cell is selected and all white cells located in the same row and all white cells located in the same column as the selected cell, including the selected cell itself, are colored black. The moves are performed until there are no more white cells.



Each solution to this puzzle can be written as a sequence of cells, where the i-th cell in the sequence is the cell that was selected on the player's i-th move. Two solutions are considered to be different if these sequences have different lengths or if there's an index i such that the i-th cells in these sequences are different. You are given a String[] field representing the initial state of the grid. The j-th character in the i-th element of field is '.' if the cell in row i, column j of the grid is initially white and 'B' if this cell is initially black. Return the number of different solutions that exist for the given grid, modulo 1000000007.
 

Definition

    
Class:DrawingBlackCrosses
Method:count
Parameters:String[]
Returns:int
Method signature:int count(String[] field)
(be sure your method is public)
    
 

Constraints

-field will contain between 1 and 20 elements, inclusive.
-Each element of field will contain between 1 and 20 characters, inclusive.
-All elements of field will have the same length.
-Each character in field will be either 'B' or '.'.
-field will contain no more than 8 'B' characters.
 

Examples

0)
    
{"."}
Returns: 1
Only one possible move.
1)
    
{"BBB",
 "BBB"}
Returns: 1
No moves are necessary here since all the cells are already black.
2)
    
{"...", 
 "BB."}
Returns: 5
Let's number rows and columns of the grid as follows: 
   012
0  ...
1  BB.


The following sequences of moves are possible (the first coordinate of each cell is its row number, the second coordinate is column number):

1. (0, 0), (1, 2);

2. (0, 1), (1, 2);

3. (0, 2);

4. (1, 2), (0, 0);

5. (1, 2), (0, 1).

3)
    
{"....................", 
 "....................", 
 "....................", 
 "....................", 
 "....................", 
 "....................", 
 "....................", 
 "....................", 
 "....................", 
 "....................", 
 "....................", 
 "....................", 
 "....................", 
 "....................", 
 "....................", 
 "....................", 
 "....................", 
 "....................", 
 "....................", 
 "...................."}
Returns: 563200757
4)
    
{"B..B",
 "B.B.",
 "...B",
 "BB.B",
 "...."}
Returns: 324

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14150&pm=10854

Writer:

Chmel_Tolstiy

Testers:

PabloGilberto , ivan_metelsky , zhuzeyuan

Problem categories:

Dynamic Programming, String Manipulation