DominoPlacement
SRM 778 · 2020-02-13 · by jy_25
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
Find the number of different ways in which the entire board can be exactly covered, modulo 109 + 7.
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.
{".."}
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
{"#.##..##..##.#..#..#.##..###...","##...##..##..#.#...#####...###.","..#..###..#.....##.####...##..#","#..#.###.#..#...#....##...#####","..##....#.##.#.#.###..#.#.####.","#.##..##..##.#..#..#.##..###..."}
Returns: 886860454
Submissions are judged against all 155 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DominoPlacement with a public method int countWays(vector<string> T) · 155 test cases · 2 s / 256 MB per case