P9646 [SNCPC2019] Paper-cutting

题目描述

剪纸是中国最古老、最受欢迎的民间艺术之一。它在地理上可以分为南方风格和北方风格。以江苏扬州、浙江乐清作品为代表的南方风格，设计巧妙美观，雕刻精美，造型有趣。北方风格以河北蔚县、丰宁为主体，以陕北作品为代表，造型夸张、气势恢宏、刻画生动、图案多样。

基本的裁剪由单个图像组成，还有对称的设计，通常是通过在成比例的折痕上折叠，然后裁成一个形状，当展开时，就形成了对称的设计。中国剪纸通常是对称的。剪纸通常是 $2$、 $4$ 、 $24$ 等偶数系列。

你会得到一张大小为 $n \times m$ 的纸， 它被划分为 $n \times m$ 个大小为 $1 \times 1$ 的块在。这张纸可以按以下方式折叠：

• 可以在两列之间选择一条垂直线，也可以在两行之间选择一条水平线。这条线把纸分成两面。

• 你用这条线作为对称轴，把小的一面折到大的一面上。如果纸的两面大小相等，从两边对折。

你想用这张纸做一幅剪纸杰作。首先，使用上述方法将纸张折叠几次（包括零次）。然后你用剪刀剪纸。每次剪切时，都可以从折叠的纸上剪切出一个连接的部分（即使从外面无法接触到该部分并将其扔掉。请注意，如果两个 $1\times 1$ 的块共享一条边，则它们是连接的。

纸张的最终外观是一个包含 $0$ 和 $1$ 的大小为 $n \times m$ 的矩阵，你想知道需要使用剪刀时的最小裁剪次数。

输入格式

有多个测试数据。输入的第一行包含一个整数 $T$ ，表示测试数据的数量。对于每个测试数据：

第一行包含两个整数 $n$ 和 $m$ ( $1 \le n \times m \le 10^6$ )表示纸张的大小。

接下来的 $n$ 行中的每一行都包含一个长度为 $m$ 的01字符串，其中 $\texttt{0}$ 表示 $1\times 1$ 块被剪切掉， $\texttt{1}$ 意味着 $1 \times 1$ 块保留在最后的剪纸上。

保证所有测试数据的 $n \times m$ 之和不超过 $10^6$ 。

输出格式

对于每个测试数据输出一行，其中包含一个整数，表示所需的最小裁剪次数。

样例 #1

样例输入 #1

4
2 5
11001
11001
5 7
1001100
0110011
0101101
0010010
1000000
3 2
11
11
11
1 8
11001100

样例输出 #1

1
4
0
1

说明/提示

对于样例一,你可以通过这种方式将唯一的 $0$ 剪出:

$$\begin{array}{ccc|cc} 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} $$

对于样例二，你可以按照以下方式折叠并裁剪出 $0$ 的 $4$ 个连通块：

$$\begin{array}{cccc|ccc} 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} $$

对于 $30\%$ 的 数据，保证所有测试数据的 $n \times m$ 之和不超过 $10^3$。
对于 $20\%$ 的 数据，保证数据随机。