P15888 [COCI 2025/2026 #6] 巧克力 / Čokolada

卢卡喜爱巧克力。他兴奋地准备享用一块生日时得到的、由 $n$ 行 $m$ 列组成的大巧克力板。巧克力由黑色和白色方格组成。然而，卢卡并不喜欢白巧克力，只想吃黑色方格。 在开始享用之前，卢卡会对巧克力进行切割。他将在巧克力的行与行之间、列与列之间进行若干次垂直或水平切割。垂直切割从巧克力的上边缘一直切到下边缘，水平切割则从左边缘一直切到右边缘。完成切割后，卢卡会得到若干块矩形巧克力片。 由于卢卡只吃巧克力中的黑色部分，他希望将黑色方格与白色方格完全分离开。这意味着，切出的每一块必须完全由黑色巧克力组成，或者完全由白色巧克力组成。 卢卡宁愿尽快开始享用，而不是把时间浪费在切割上，因此他请你帮助确定，为了将黑色方格与白色方格分离，所需的最少切割次数。 :::align{center}  ::: 图 1：第一个样例中，为了以最少的切割次数将黑色部分与白色部分分离，巧克力应按图示方式切割。

第一行包含两个自然数 $n$ 和 $m$（$1 \le n, m \le 200$），分别表示巧克力的行数和列数。 接下来的 $n$ 行，每行包含 $m$ 个字符，每个字符为 $0$ 或 $1$。字符 $0$ 表示白色方格，$1$ 表示黑色方格。

输出一行一个整数，表示将黑色方格与白色方格分离所需的最少切割次数。

**第一个样例的解释：** 如图中所示。 **第二个样例的解释：** 卢卡应在第 1 行与第 2 行之间、第 3 行与第 4 行之间、第 1 列与第 2 列之间、第 3 列与第 4 列之间各切一刀。 **第三个样例的解释：** 卢卡应在每两行之间和每两列之间都切一刀，总共 $6$ 刀。 | 子任务 | 分值 | 限制 | |:-:|:-:|:-| | 1 | 5 | 巧克力为棋盘格状，即第 $i$ 行第 $j$ 列的方格，当 $i+j$ 为偶数时为白色，奇数时为黑色。 | | 2 | 11 | $n = 1$ | | 3 | 11 | 恰好有一个黑色方格。 | | 4 | 23 | 无额外限制。 | 翻译由 DeepSeek V3.2 完成