JOIN
Get Time

   Problem Statement  

 Problem Statement for TBlocks

Problem Statement

    

Fox Ciel has an unlimited supply of T-shaped tetrominoes. We will call them T-blocks. One T-block is shown in the picture below. The green cell is called the center of the T-block.







Ciel also has a rectangular board divided into square cells. The cells of the board have the same size as the cells of her T-blocks. Each cell is marked 'o', '*', or '-'. Ciel wants to place some T-blocks onto this board in a way that satisfies the following conditions:

  • Each T-block covers precisely 4 cells of the board. (Thus, each T-block must be placed completely inside the board.)
  • No two T-blocks overlap. (They are allowed to touch each other.)
  • The center of a T-block can only be placed on cells marked 'o' and '*'.
  • Each 'o' cell has to contain the center of some T-block.


You are given a String[] board that represents Ciel's board using the characters specified above. Return the number of valid ways in which T-blocks can be placed onto this board, modulo 1,000,000,007.

 

Definition

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

Constraints

-board will contain between 1 and 50 elements, inclusive.
-Each element of board will contain between 1 and 50 characters, inclusive.
-Each element of board will contain the same number of characters.
-Each character of each element of board will be 'o', '*' or '-'.
-board will contain between 0 and 500 'o's, inclusive.
-board will contain between 0 and 12 '*'s, inclusive.
 

Examples

0)
    
{"---"
,"-o-"
,"---"}
Returns: 4
We have to place exactly one T-block. Its center has to be on the middle cell. There are 4 ways to do this:



1)
    
{"o"}
Returns: 0
There isn't enough space to place a T-block here.
2)
    
{"**-"
,"-**"}
Returns: 3
Some '*' cells may remain empty. They may also contain T-block cells other than the center.



3)
    
{"----"
,"-o*-"
,"--*-"
,"----"}
Returns: 7
4)
    
{"--"
,"--"
,"--"}
Returns: 1
5)
    
{"-----o------o-----o---o------o-----o--------------"
,"-o--------o---o-----------o----o-----o--o---o-o--o"
,"----o-o-o--o-------*-o---o--o---o--o---o--o-------"
,"-o-----------o-oo-------------o------o---------o--"
,"---o-o-o--o-------o-o--o--o------oo-----o---*--o--"
,"--o---------o-o-------------o--o-----o---o-------o"
,"o---o---oo---------o--o--o-------------o---*------"
,"--o---o------o---o---------*-o--o-o------o---o-oo-"
,"------o---o----o-----o--o------------o------------"
,"-o-o----o---o-----o-------o---oo---o----o--o--o---"
,"------o-------o-o----o--o---o----o---o----------o-"
,"----o----oo--------o-o----o---o----o---o----o--o--"
,"--o-----------o-----------o-----o---------o------o"
,"o-----o-----o----o-----o----o----o---o------o-o---"
,"---o-----o-----o----o----o----o--------o--------o-"
,"-o----o------o----o-----o---o---o---o----o-----o--"
,"--------o--o----o----o-------o--------o-----o----o"
,"----o-----o---o---oo---o-o-----o--o------o----o---"
,"-o----o-o----o--o----o-----o--------o--o---o--o-o-"
,"---o------------o--o--------------o---------------"
,"-----o-o--o---o--------o--*--o--o----o---o-o---o--"
,"-o-------o-------o---o--o----------o---o----o-----"
,"----o-o-----o--o---o-------o--o------o----o-----o-"
,"-o--------o---------o--o-o------o--o-----*----o---"
,"-----o-o-----o--o-o---------o------o---o----------"
,"-o-o-----o-o-------o--o--o----o------o--o---o--o-o"
,"------o--------o-o-----o----o---o-*---------------"
,"-o--o-----o---------o-----------------o---*o----o-"
,"----o---o---o-o---o-----o--o---oo--o----o----o----"
,"------*----o---------o-------o--------o----------o"
,"o--*-----o-----o---o---o---o--o--o--o----o--o-oo--"
,"--o----o---o-----o-------o-------------o-o--------"
,"----o----o---o-o-----o----o-----o-o--o-------o--o-"
,"------o---o-------------o---o-o---------o--o------"
,"-o--o-------o-o--o-o--o---------o--o-o-----o--o---"
,"------o-o--------o-------o---o---------o--------o-"
,"--o----------o-o-----o-----o------o-o-----o--o----"
,"---------o-o------o----o------o---------o--o-----o"
,"o--o-o----------o---o----o---o--o--o--o-------o---"
,"-------o---oo-o-------o----o---o--o-----o-o-----o-"
,"-o--o---o-------o--o----o----o------oo-------o----"
,"-----o----o----------*-----o-----o------o-o-------"
,"o-o----o----o---o--o---o-----o-o------o-----o-o-o-"
,"----o----o----o-------o---o-------o-o----o--o-----"
,"-o----o----o------o-----------o--------o------o--o"
,"-----o--o---o--o----o----oo-o---o-----o----o------"
,"o--o------o-------o----o----------*--------o----o-"
,"-------o-o---o-------o-------o--o---o----o----o---"
,"-o--oo----------oo-o----o--o-----------o----o----o"
,"--------o--o--o-------o-------o---o--o---o-----o--"}
Returns: 481632789

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:
       2013 TCO Algorithm Championship Round - Division I, Level Three