
ZOJ Problem Set  4132
Papercutting is one of the oldest and most popular folk arts in China. It can be geographically divided into a southern and a northern style. The southern style, represented by works from Yangzhou in Jiangsu Province and Yueqing in Zhejiang Province, features ingenious and beautiful designs, exquisite carving and interesting shapes. The northern style, mainly from Yuxian and Fengning in Hebei Province and best represented by works from northern Shaanxi, features exaggerated shapes, vigorousness, vivid depictions, and diverse patterns. There are basic cutouts, consisting of a single image, and symmetrical designs, that are usually created by some folding over a proportioned crease, and then cutting a shape, so that when unfolded, it forms a symmetrical design. Chinese paper cuttings are usually symmetrical. The paper cutouts are usually in an even number series of $2$, $4$, $24$, etc. You are given a piece of paper in the shape of a matrix of size $n \times m$ and it is partitioned into $n \times m$ blocks of size $1 \times 1$. The piece of paper can be folded in the following way:
You would like to make a papercutting masterpiece from this paper. At first, you fold the paper using the method above several times (including zero times). Then you use scissors to cut the paper and each time you can cut out a connected component from the paper and throw it away. Note that two $1 \times 1$ blocks are connected if they share an edge. Given the final look of the paper  a matrix of size $n \times m$ containing $0$s and $1$s, you would like to know the minimum number of cuts needed when using the scissors. InputThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case: The first line contains two integers $n$ and $m$ ($1 \le n \times m \le 10^6$)  the size of the paper. Each of the next $n$ lines contains a binary string of length $m$, where '0' means the $1 \times 1$ block is cut out and '1' means the $1 \times 1$ block remains on the final papercutting. It is guaranteed that the sum of $n \times m$ over all test cases does not exceed $10^6$. OutputFor each test case output one line containing one integer, indicating the minimum number of cuts needed. Sample Input3 2 5 11001 11001 5 7 1001100 0110011 0101101 0010010 1000000 3 2 11 11 11 Sample Output1 4 0 HintFor the first sample test case, you can fold in the following way and cut the only $0$ out: $$\begin{array}{ccccc} 1&1&0&0&1\\1&1&0&0&1\end{array} \to \begin{array}{ccc} 1&1&0\\ \hline 1&1&0\end{array} \to \begin{array}{ccc} 1&1&0\end{array}$$ For the second sample test case, you can fold in the following way and cut the $4$ connected components of $0$s out: $$\begin{array}{ccccccc} 1&0&0&1&1&0&0\\0&1&1&0&0&1&1\\0&1&0&1&1&0&1\\0&0&1&0&0&1&0\\1&0&0&0&0&0&0\end{array} \to\begin{array}{cccc} 1&0&0&1\\0&1&1&0\\0&1&0&1\\0&0&1&0\\1&0&0&0\end{array}$$ Author: LIN, Xi Source: The 2019 ICPC China Shaanxi Provincial Programming Contest 