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

1. {"---"
   ,"-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:

2. {"o"}

   Returns: 0

   There isn't enough space to place a T-block here.

3. {"**-"
   ,"-**"}

   Returns: 3

   Some '*' cells may remain empty. They may also contain T-block cells other than the center.

4. {"----"
   ,"-o*-"
   ,"--*-"
   ,"----"}

   Returns: 7

5. {"--"
   ,"--"
   ,"--"}

   Returns: 1

6. {"-----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