All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
We call an N × M matrix nice, if it satisfies both these conditions:
- Each of its elements is either a 0 or a 1.
- We define two cells of the matrix to be adjacent, if they share a side. All the cells containing a 1 should form a single connected component.
More formally: You should be able to reach any cell containing a 1 from any other cell containing a 1 through a sequence of steps, where a single step consists of moving from one cell containing a 1, to an adjacent cell containing a 1.
You are given an N × M matrix A, and each of its elements is either a 0 or a 1. You want to decompose A into some terms, where each term is a sign ( + or - ) followed by a nice matrix. In other words, you want to write A as the addition and subtraction of some nice matrices.
For example, you could write A = + B1 + B2 - B3 + B4 - B5, where each Bi is a nice matrix. Note that even though every single Bi and their total sum (which equals A) has only elements 0 and 1, some prefix sum could have other elements. For example, the matrix corresponding to + B1 + B2 - B3 could have elements which are neither 0 nor 1.
Find the smallest number of nice matrices needed to decompose A in the manner described above and output them. If there are multiple ways to do this, you can output any one optimal decomposition.
The first line of the input contains an integer T denoting the number of test cases.
The first line of every test case contains two integers, N and M, which denote the number of rows and number of columns respectively.
The i-th of the following N lines contains a string of length M and consisting only of characters '0' and '1', which denotes the i-th row of the matrix A.
For each test case, first output a line with a single integer k, which denotes the smallest number of nice matrices needed to decompose A.
This should be followed by k * (N + 1) lines, which correspond to the k terms.
Each term should have N + 1 lines. The first line of each term should contain either a '+' or a '-', which denotes whether the following nice matrix is to be added or subtracted. The following N lines should denote the N rows of the nice matrix, with each line containing a string of length M.
- 1 ≤ T ≤ 103
- 1 ≤ N, M ≤ 20
- There will be at most 100 test cases where N > 10 or M > 10.
- The matrix A is guaranteed to have at least one non-zero element.
Input: 1 3 4 1010 0101 1010 Output: 3 - 0000 0010 0000 + 1010 1111 1010 - 0000 1000 0000
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.