题目概括

现有 $n \times m$ 的巧克力，其上有黑白两种颜色。最少需要多少次切割才能使黑白分离？

思路讲解

由于我们只能行切割或列切割，所以我们定义 $hq$ 为横切数，$sq$ 为竖切数。

此外，观察样例可知：

• 若第 $i$ 行与第 $i+1$ 行不相同，$hq \gets hq+1$。
• 若第 $j$ 列与第 $j+1$ 列不相同，$lq \gets lq+1$。

因为若行或列不同，就会出现黑白交错的情况。

所以总切割数为 $hq+lq$。

代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
string a[250];
int hq, sq;
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n - 1; i++)
		if (a[i] != a[i + 1]) hq++;	 // 比较每一行。若相邻两行不同，横切数 + 1
	for (int j = 0; j < m - 1; j++)	 // 每一列
	{
		bool f = 1;					 // 是否相同
		for (int i = 0; i < n; i++)	 // 比较每一列的每一行
		{
			if (a[i][j] != a[i][j + 1]) {
				f = 0;	// 若有一个不相同，停止判断
				break;
			}
		}
		if (!f) sq++;  // 如果不一样，竖切数 + 1
	}
	cout << hq + sq;  // 结果
	return 0;
}

AC 记录。