Connection Status:
Competition Arena > DominoTiling

DominoTiling

SRM 722 · 2017-10-11 · by erinn

SRM 722 · 2017-10-11 · by erinn · Brute Force
Class Name: DominoTiling
Return Type: long
Method Name: count
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You are given a String[] grid that describes a rectangular grid of square cells. The character 'X' represents a cell that is already covered, the character '.' is a cell that still needs to be covered.

You want to cover all the '.' cells using a collection of disjoint 2x1 dominos. Return the number of ways to do this. Two ways are considered different if two cells are covered by the same domino in one tiling and by two different dominos in the other tiling.

Constraints

  • grid will contain between 1 and 12 elements, inclusive.
  • The length of each element of grid will be between 1 and 12, inclusive.
  • Each element of grid will be the same length.
  • Each character of each element of grid will be '.' or 'X'.
Examples
0)
{"..",
 ".."}
Returns: 2

There are exactly two ways to do this: -- or || -- ||

1)
{"...",
 ".X.",
 "..."}
Returns: 2

Again, there are two solutions: --| |-- |X| |X| |-- --|

2)
{"...",
 "...",
 "..X"}
Returns: 4

||| --| |-- --| ||| --| |-- ||| --X __X --X ||X

3)
{".....",
 ".....",
 ".X...",
 ".X..."}
Returns: 29
4)
{"..","..",".."}
Returns: 3

Submissions are judged against all 17 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class DominoTiling with a public method long long count(vector<string> grid) · 17 test cases · 2 s / 256 MB per case

Submitting as anonymous