P3969 [TJOI2014] Puzzle

Little Z has recently become obsessed with jigsaw puzzles, but with limited intelligence, he always fails to complete the full picture. The game works like this: first, Little Z is given some puzzle pieces. He then tries to rearrange these pieces so that they form a $4 \times 4$ square, as shown below. Note that Little Z cannot rotate or flip the pieces. Little Z gets the pieces shown in Figure 1, and after rearranging them, he obtains the $4 \times 4$ square shown in Figure 2. Since Little Z is really not good at this, please write a program to help him solve the problem.

The input contains multiple test cases; read until EOF. For each test case, the first line contains a positive integer $N$, the number of pieces. Then $N$ pieces follow. For each piece, the first line contains two positive integers $r$ and $c$, the number of rows and columns of this piece. Then there are $r$ lines, each containing $c$ characters '0' or '1'; '1' means the piece occupies that cell, and '0' means the cell is empty. It is guaranteed that each piece is a single connected component (i.e., the '1's are connected), and there is no row or column consisting entirely of '0's.

If it is impossible to form a square, output "No solution". If there are multiple solutions, output "Yes, many!". Otherwise, output "Yes, only one!", and then output a $4 \times 4$ matrix $H$, where $H_{i,j}$ denotes the index of the piece at position $(i, j)$. Piece indices start from $1$.

### Constraints - For $30\%$ of the test cases, $N < 5$. - For $100\%$ of the test cases, $N \le 16$. Translated by ChatGPT 5