DominoTilings
2018 TCO Semi 1 · 2018-11-14 · by misof
Problem Statement
You are given a
- Choose any R times C rectangle such that R is at most 13 and R*C is at most 14,400.
- Within that rectangle, draw a 4-connected shape that has exactly n different domino tilings.
- Return your shape formatted as a
String[] with R elements, each containing C characters. Use '.' for cells that belong to your figure and '#' for cells that don't. (Recall that all '.'s must form one 4-connected component.)
You may assume that a solution always exists. If there are multiple solutions, you may return any of them.
Notes
- A domino is a 2x1 figure that can be used to cover two adjacent cells of the grid (either horizontally or vertically).
- A domino tiling is a collection of dominoes that covers each '.' cell exactly once and no other cells.
- Two tilings are considered different if two cells are covered by the same domino in one tiling and by two different dominoes in the other tiling.
- Two cells that belong to the figure are directly connected if they share a side. A figure is 4-connected if each pair of cells in the figure is connected, either directly or via other cells.
Constraints
- n will be between 2 and 1018, inclusive.
2
Returns: {"##########...##########", "##########.#.##########", "##########...##########" }
The returned figure is just a 3x3 square with a hole in the middle. It has two tilings: --| and |-- |#| |#| |-- --|
4
Returns: {"##########...##########", "##########...##########", "##########..###########" }
The returned figure is just a 3x3 square with a hole in a corner. It has four tilings: ||| --| |-- --| ||| --| |-- ||| --# --# --# ||#
36
Returns: {"##########....##########", "##########....##########", "##########....##########", "##########....##########" }
196
Returns: {"#########.....#########", "#########.....#########", "#########..#..#########", "#########.....#########", "#########.....#########" }
259009513044645817
Returns: {"......................", "......................", "......................", "......................", "......................", "......................", "......................" }
Submissions are judged against all 54 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DominoTilings with a public method vector<string> solve(long long n) · 54 test cases · 2 s / 256 MB per case