eolymp
bolt
Try our new interface for solving problems
Problems

Nonogram

Nonogram

\textit{Nonogram} is a logic puzzle with simple rules and challenging solutions. The rules are simple. You have a grid of squares, which must be either filled in black (we denote this with \textbf{1}) or marked with \textbf{X}/blank (we denote this with \textbf{0}). Beside each row of the grid are listed the lengths of the runs of black squares on that row. Above each column are listed the lengths of the runs of black squares in that column. Your aim is to find all black squares. \InputFile The first line contains the number \textbf{t }of nonogram puzzles that you have to solve. Each test case starts with a blank line, followed by two positive integers \textbf{w }and \textbf{h }in the next line that denote the width and the height of the puzzle. We guarantee that \textbf{1 }≤ \textbf{w * h }≤ \textbf{20}. Then there will be two blocks of puzzle description that started with a blank line: one for rows (that contains \textbf{H }lines) and another for columns (that contains \textbf{w }lines). In those two blocks, you will be given comma separated values that denote the lengths of the runs of black squares in each row/columns (note: it can be blank). \OutputFile For each test case (puzzle), determine if the answer is unique. If it is unique, output a \textbf{2D }binary matrix of \textbf{h }lines containing \textbf{w }characters. Put \textbf{1 }if the corresponding cell is black, or \textbf{0 }otherwise. If it is not unique, just print "\textbf{not unique}" in one line (without \textbf{"}). Separate the output of two test cases with a blank line. \includegraphics{https://static.e-olymp.com/content/f8/f8e8e3ae7b82c797891a2432414972b22d98039e.jpg}
Time limit 3 seconds
Memory limit 128 MiB
Input example #1
3

5 4

3
1,2
1,1
2

3
1
1
1,1
3

7 2

1,1,1,1
1,1,1

1
1
1
1
1
1
1

7 1

1,3,1

1

1
1
1

1
Output example #1
11100
10011
10001
00011

1010101
0101010

1011101
Author Dr. Steven Halim
Source 2013 ACM-ICPC Thailand Southern Programming Contest, August 10, Problem E