Description
Nonogram is a puzzle solving game.
The rule of solving Nonogram is simple,
you are given a empty 2D grid, and your goal is to color some grid to fit given conditions.
There are a list of numbers beside each row and column,
the list of numbers tells you the length of each consecutive colored grid of that row/column.
For example, if see '1 2 3' in row 1, then there will be 1 colored grid, followed by one or more empty grid, then exactly 2 consecutive colored grids, followed by one or more empty grid, then exactly 3 consecutive colored grids, from left to right.
Also, if see '2 2' in colum 2, then there will be exactly 2 consecutive colored grids, followed by one or more empty grid, then exactly 2 consecutive colored grids, from up to down.
If all lists on each row and column are 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 asked you to verify wherther the Nonogram she colored is correct or not.
As an engineer, we should make everything automatically. So just build a Nonogram Validator!
ouo.
For the first Nonogram in the sample input, the input is as follow:
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 colored grids that is length 1,
for the second row, there are exactly 3 colored grids that is length 1,
...
for the first column, there are exactly 2 colored grids and they are consecutive, so the length is 2,
for the second column, there are exactly 2 colored grids that is length 1,
...
So the answer is "Yes".
For the second Nonogram in the sample input, the input is as follow:
the grid at the third row and the third column should be a 'o' so the Nonogram is correct,
so the output should be a "No".
Testcases have changed and rejudge since some code are not allow to pass but pass.
Sorry for the inconvience.
Rejudge finished @2020/10/29 22:50.
Input
The first line contains of an integer T,
represent that your sister has just finished T Nonograms.
Then for each Nonogram,
The first line contains 2 integers N, M,
represent the rows and the colomns of the Nonogram respectively.
Then the following N lines,
there are an integer Row_Li represent the length of the list beside the ith row,
then follows by Row_Li integers, separated by spaces, represent numbers of the list beside the ith row,
the numbers in the list is given from left to right.
Then the following M lines,
there are an integer Col_Li represent the length of the list beside the ith column,
then follows by Col_Li integers, separeted by spaces, represent numbers of the list beside the ith column,
the numbers in the list is given from up to down.
The the following N lines, each line has M characters,
represent the Nonogram your sister has finished,
the character 'o' represent that the grid is colored,
the character 'x' represent that the grid is not colored and empty.
It is a guarantee that:
1 <= T <= 10,
1 <= N, M <= 45
the given list of numbers is always valid.
Output
Output should contains T lines,
for each Nonogram,
output "Yes" (without quotes) if the Nonogram is solved correctly,
otherwise, output "No" (without quotes).