Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 1080
Direct Subtraction

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Statement of the Problem

Some algorithms on image processing are more efficient when applied to small patterns, such as 3 x 3 matrices. One way of decomposing a given figure into small components is to apply the operation of direct subtraction, which is described in the following.

Given a 0/1 matrix Amxm and a 0/1 matrix B3x3 we define the matrix C(m-2)x(m-2) = A - B obtained in the following way:

We call matrix C a valid direct subtraction of B from A if for every aij = 1 in matrix A, there is a 1 in matrix C which results from a subtraction of B from a submatrix of A containing aij, and the element of B which is subtracted from aij is equal to 1.

Example: Given matrices A and B,

the direct subtraction C = A - B is valid and is given by

Now, given matrices A and B,

The direct subtraction C = A - B is not valid and is given by

The objective of this problem is to determine if a matrix A can be transformed into a 3 x 3 matrix through a sequence of valid direct subtractions of, possibly different, 3 x 3 matrices.

Input Format

Several input instances are given. Each instance begins with the dimension 0 < n < 20 of the matrix to be decomposed. The following n lines describe the rows of that matrix, as a sequence of n 0's and 1's, with no blank spaces between them. The input ends with a line with a single 0.

Output Format

For each input instance your program must identify it by printing Instance i: (where i is the number of the instance) and, in the next line a message Yes or No for the case, resp. that the matrix is (resp. is not) decomposable.

Sample Input

5
01010
11111
01111
00111
00010
5
10001
00000
00100
00000
10001
0

Sample Output

Instance 1:
Yes
Instance 2:
No


Source: South America 2001
Submit    Status