Matrix Sum

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 = + B_{1} + B_{2}  B_{3} + B_{4}  B_{5}, where each B_{i} is a nice matrix. Note that even though every single B_{i} 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 + B_{1} + B_{2}  B_{3} 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.
Input
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 ith of the following N lines contains a string of length M and consisting only of characters '0' and '1', which denotes the ith row of the matrix A.
Output
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.
Constraints
 1 ≤ T ≤ 10^{3}
 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 nonzero element.
Example
Input: 1 3 4 1010 0101 1010 Output: 3  0000 0010 0000 + 1010 1111 1010  0000 1000 0000
Author:  alex_2oo8 
Tags  alex_2oo8 
Date Added:  20062017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 