Fix Flooded Floor
InterviewTime limit3sMemory limit2048 MB
Given a 2xn grid where '#' marks blocked cells and '.' marks empty cells, decide if the empty cells have exactly one, multiple, or no tilings with 1x2 dominoes.
- Level
Medium5 of 10
- Topics
- Dynamic programming, Implementation
- Solved
- No attempts yet
Statement
Archimedes conducted his famous experiments on buoyancy. But not everyone knows that while he was taking a bath, he was too focused and didn't notice the moment when the water overflowed over the edge of the bath and flooded the floor near the wall. His expensive parquet was irreversibly damaged!
Archimedes noticed that not all was lost, and there were still several undamaged parquet pieces. The parquet near the wall had the shape of a long narrow stripe of cells. Archimedes had an unlimited supply of parquet pieces that could be placed parallel or perpendicular to the wall. Archimedes didn't want to cut the parquet pieces. As a great scientist, he figured out that there was exactly one way to restore the parquet by filling the damaged area of the parquet with the non-overlapping cell shaped pieces.
Help historians check Archimedes' calculations. For the given configuration of the parquet floor, determine whether there is exactly one way to fill the damaged parquet cells with the cell parquet pieces. If Archimedes was wrong, find out whether there are multiple ways to restore the parquet, or whether there are no ways at all.
Input
The first line contains a single integer (), the number of test cases to solve. Then the description of test cases follows.
The first line of each test case contains a single integer (), the length of the parquet floor. The following two lines contain exactly characters each and describe the parquet, where . denotes a damaged cell and # denotes an undamaged cell.
The total sum of in all test cases doesn't exceed .
Output
For each test case, print Unique if there is exactly one way to restore the parquet, Multiple if there are multiple ways to do so, or None if it is impossible to restore the parquet.