Drift Puzzle#3826
A common puzzle involves listing a sequence of three frames (F_1, F_2, F_3) of an animation, and asking for the "most logical" fourth frame F_4. For example:
Usually the puzzle is posed as a multiple-choice question. This is boring. A more interesting problem is to find the fourth frame directly!
To be precise, we will consider animation frames that are constructed using the following rules:
Every frame F_i is a grid with height and width .
Every frame F_i contains distinct objects m_1 = A, m_2 = B, m_3 = C, ..., m_n = (\text{letter}).
Each object m_j in each frame is located in one of h \times w cells, and may overlap.
If two objects m_j and m_k, j < k, occupy the same cell, then only m_j (i.e., the object with lesser index) would be visible.
Each object m_j has a fixed, non-zero "drift velocity": from F_i to F_{i+1}, m_j travels unit in one of eight possible (horizontal, vertical or diagonal) directions.
If an object moves outside the grid, it "wraps around" to the opposite side (or corner).
In the example shown, we can deduce that drifts eastward; drifts south-westward; drifts northward; drifts northward; and drifts north-westward. In F_2, and occupy the same cell, so only is visible. In F_3, drifts beyond the west wall and wraps around on the east side (while also moving south by one unit). Using the above information, we can extrapolate the trajectory of each object and find F_4:
Since objects cover one another, F_1, F_2 and F_3 may not provide enough information to solve for the velocities of each object. Therefore, F_4 can have multiple solutions (see Sample Input case ); when this happens you should output an error message. Sometimes objects can have many possible velocities, but a unique solution for F_4 would still exist (see Sample Input case ); in this case F_4 is well-defined, and should be solved.
The first input line contains the number of test cases , 1 \leq N \leq 50.
Each test case begins with a line containing integers , and , separated by space. lines follow. On each line , 1 \leq i \leq h, three space-separated length- strings a_i, b_i and c_i are given. The text block a_1, a_2, \dots, a_h, when stacked vertically, specifies F_1. Similarly, b_1, b_2, \dots, b_h and c_1, c_2, \dots, c_h specify the F_2 and F_3, respectively.
is the height of each frame, and satisfies 3 \leq h \leq 10.
is the width of each frame, and satisfies 3 \leq w \leq 10.
is the number of distinct objects, and satisfies 1 \leq n \leq 26.
For 1 \leq i \leq h, each a_i, b_i and c_i are length- strings consisting of uppercase alphabets "A"–"Z" (for objects) or the period "." (for empty spaces).
F_1, F_2 and F_3 from inputs will follow the animation construction rules outlined above, so F_4 is guaranteed to have at least one solution.
For each test case, if a unique F_4 exists, then print it in the same format as the input, i.e., as lines of length- strings. Otherwise print Multiple solutions exist on a single line. Print an empty line between test cases, but not after the last test case.
For Test Case , two possible solutions for F_4 are
ABC ABC
DE. DEF
depending on whether drifts northward or drifts westward; so multiple solutions exist.
For Test Case , may drift eastward, southward or south-eastward, but all three cases would lead to the same F_4, so a unique solution exists.
For Test Case , - are covered by , and - are covered by or . Therefore, the location of some blocks is ambiguous. However, a unique solution exists.
For Test Case , two possible F_4's are
..... .....
..C.. ..C..
..... .....
A.... A..D.
.B... .B...
Example 1