| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12446 | Bacteria Widespread |
|
| 12936 | Let's build a Nonogram Validator |
|
Description
Hey, can I say somthing amazing? Bacteria touched the air for some reason and begin to widespread in the classroom. The bacteria turned out to be Firmicutes (some kind of bacteria). The classroom can be viewed as a 2D grid map with size R x C. Walls in classroom are denoted as #, clean areas not polluted by Firmicutes are denoted as C, and places where there exist Firmicutes are denoted as F. The classroom is guaranteed to be surrounded by walls. For example a classroom of size 7 x 8 with some area polluted may look like this :
######## #CCC#CC# #CFC#### #CCCCCC# #CC##### #FCCCCC# ########
Firmicutes reproduces rapidly. Initially, some areas in the classroom are polluted by Firmicutes. For every second, if an area is polluted by Firmicutes, the Firmicutes on this area will reproduce themselves and spread to neighboring clean areas. Here, we define neighboring areas of area (r, c) are (r+1, c), (r-1, c), (r, c+1), and (r, c-1). Note that Firmicutes cannot spread onto walls, which means that even if a wall is neighbor to some polluted area, the wall will not be polluted. The following example is a classroom from t = 0 ~ 2 seconds.
Initially, t=0. Some areas are polluted.
######## #CCC#CC# #CFC#### #CCCCCC# #CC##### #FCCCCC# ########
When t=1,
######## #CFC#CC# #FFF#### #CFCCCC# #FC##### #FFCCCC# ########
When t=2,
######## #FFF#CC# #FFF#### #FFFCCC# #FF##### #FFFCCC# ########
Given how the class looks like initially (when t=0) and a time T, please output how the classroom looks like when t=T.
Input
The first line consist of three integers R, C, T, meaning the size of the classroom and a time.
For the following R lines, each line has C characters, being how the classroom looks like initially. Each character will be one of {#, C, F} and the classroom is surrounded by walls (#).
Technical Restrictions
-
3 ≦ R, C ≦ 100
-
0 ≦ T ≦ 100
-
The first test case is same as sample IO. It is suggest to use it to check whether your output format is valid.
Output
Please output how the classroom looks like in the T-th second (when t=T).
Sample Input Download
Sample Output Download
Tags
Discuss
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.
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 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,
...
So the answer is "Yes".
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,
so the output should be a "No".
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 <= 45
and the given lists of numbers are always valid.
Output
Output should contain T lines:
for each Nonogram,
output "Yes" (without quotes) if the Nonogram is solved correctly;
otherwise, output "No" (without quotes).