DominoPlacement | Topcoder Archive

Problem Statement

For each positive integer k, you have an infinite supply of dominos of shape 1 * k. Each domino can be placed either horizontally or vertically.

You have a rectangular board. Some cells of the board are already covered by 1 * 1 dominos, the rest is empty. You are given the description of the board in the String[] T . The character '.' represents an empty cell, the character '#' a cell that is already covered.

Find the number of different ways in which the entire board can be exactly covered, modulo 10⁹ + 7.

Definition

Class:: DominoPlacement
Method:: countWays
Parameters:: String[]
Returns:: int
Method signature:: int countWays(String[] T)
(be sure your method is public)

Notes

A board is exactly covered if each cell is covered by exactly one domino, and each domino is completely inside the board.
Two coverings of the board are different if there are two (not necessarily distinct) cells P and Q such that in exactly one of the two coverings there is a domino whose ends cover P and Q.

Constraints

All strings in T will have the same length.
Each character of each string in T will be '.' or '#'
The total number of characters in T (i.e., the area of the board) will be between 1 and 300, inclusive.

Examples

```
{".."}
```
```
Returns: 2
```
One can either use a single 1 * 2 domino or two 1 * 1 dominos, giving 2 different ways.
```
{".#",
 ".."}
```
```
Returns: 3
```
If we keep a 1 * 1 domino at the top left cell, we have 2 ways to fill the bottom two empty cells like in the last test. If we place a vertical 1 * 2 domino instead, we must place a 1 * 1 domino at bottom right cell. The total number of ways is therefore 2 + 1 = 3. All three tilings are shown below (with different letters representing different dominos). A# A# A# BC AB BB
```
{".#.",
 "#..",
 "..."}
```
```
Returns: 20
```

{"#######.#####",
 "...#....#....",
 "...#....#....",
 "...#....#....",
 "...#....#####"}

Returns: 426089093

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)2024, Topcoder, Inc. All rights reserved.