| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14138 | Nonogram Corrector |
|
Description
Nonogram is a puzzle solving game.
The rule of solving Nonogram is simple:
you are given an empty 2D matrix, and your goal is to color some grid to fit given conditions.
There is a list of numbers beside each row and column,
which tells you the length of each consecutive colored grid of that row/column.
If the list on each row and column is fit, then the Nonogram is solved.
Your sister just tells you that she finished her summer homework,
and her homework is to solve Nonogram!
She asks you to verify wherther the Nonogram she colored is correct or not.
Since she is smart, she will make at most two mistakes in one nonogram. Please help her find out the answer of each nonogram. If her answer is already correct, directly output it; otherwise, correct the mistakes (can be one or two) and output the correct nonogram.
As an engineer, we should make everything automatically. So just build a Nonogram Corrector!
ouo.
For the first Nonogram in the sample input, the input is as follows:
notice that the order of the input is blue arrows from up to down, then green arrows from left to right.
For the first row, there are exactly 2 consecutive colored grids both of length 1,
for the second row, there are exactly 3 consecutive colored grids all of length 1,
...
for the first column, there is 1 consecutive colored grid of length 2,
for the second column, there are exactly 2 consecutive colored grids both of length 1,
...
Therefore, this is a correct nonogram, and you should directly output it.
For the second Nonogram in the sample input, the input is as follows:
the grid at the third row and the third column should be a 'o' so that the Nonogram can be correct.
Therefore, you need to change it into 'o' and output the modified nonogram.
Input
The first line contains an integer T,
representing that your sister has just finished T Nonograms.
Then for each Nonogram, the first line contains 2 integers N, M, representing the numbers of rows and columns of the Nonogram, respectively.
Then for each of the following N lines,
there is an integer Row_Li representing the length of the list beside the ith row,
followed by Row_Li integers, separated by spaces, representing the numbers of the list beside the ith row,
where the numbers in the list are given from left to right.
Then for each of the following M lines,
there is an integer Col_Li representing the length of the list beside the ith column,
followed by Col_Li integers, separeted by spaces, representing the numbers of the list beside the ith column,
where the numbers in the list are given from up to down.
Lastly, each of the following N lines has M characters,
representing the Nonogram your sister has finished, where
the character 'o' represents that the grid is colored, while
the character 'x' represents that the grid is not colored and empty.
It is guaranteed that:
1 <= T <= 10,
1 <= N, M <= 20
and the given lists of numbers are always valid.
For testcases 1~7: There is at most one mistake in each nonogram.
For testcases 8~10: There are at most two mistakes in each nonogram.
Output
If the nonogram is already correct, just output it; otherwise, fix the mistakes in it and print it.
There is an '\n' in the end.