Theater
In this question, you are to help the owner of a theater in Bangkok. The theater has R rows and each row has 8seats. Some of these seats are already reserved in advance. Now, you have some customers wanting to see the movie. There are two types of customers. The first type is those who are single. The other type is those who come as a couple. Naturally, a couple wants to sit next to each other. Also, if possible, each single and each couple do not want to sit next to or behind another person. The customers will be very happy if these constraints can be met.
Your task in this problem is hence to determine if that is possible. Specifically, you are given the seats that already reserved, the number of singles S and the number of couple C, you are to determine if it’s possible to seat them such that all of the followings are met for all singles and couples:
Single can only be seated at a non-reserved seat.
Single does not sit next to any person in the same row.
Single does not sit directly behind any person in the adjacent row in front of him/her.
Couple can only be seated at two adjacent non-reserved seats in the same row.
Couple does not sit next to any person in the same row, except his/her partner.
Couple does not sit directly behind any person in the adjacent row in front of him/her.
Note: person is defined to be another single, another couple or a reserved seat, as there will be someone sitting there.
The reserve seats do not need to satisfy any of these constraints, as the customer who reserved the seats are happy to sit there regardless.
Input
First line of input is a number of test cases T ≤ 20.
Each test case starts with a line containing three numbers, R, S, C (1 ≤ R ≤ 20, 0 ≤ S ≤ 30, 0 ≤ C ≤ 30). The next R lines represent the rows in the theater starting from the front-most row to the back-most row. Each line is a binary string of length 8 where 0 indicates that a seat is non-reserved and 1 indicates that a seat is reserved.
Output
For each test case, display YES if it’s possible to satisfy all requirement. Otherwise, the line should be the string NO.
Explanatoin: A possible seating for input 1 that satisfy all the requirement is (s indicates single, c indicates couple)
A possible seating for input 2 is:
There is no possible seating to satisfy all constraints for input3.