思路

模拟题，根据题意进行贪心模拟即可。 我们需要将所有非 1 的字符全部修改为 1 ，所以一旦遇到一个为 1 的字符，就将其修改为 1 ，并将其相邻的字符也一并修改为 1。 这里我们考虑将当前字符以及其右边的字符修改为 1 的贪心方式，这样遍历的同时进行修改，使得最终需要进行修改的字符数量最少即可。 时间复杂度：$O(nm)$

代码

python

n, m = map(int, input().split())

题目描述

小红拿到了一个01矩阵，她每次操作可以选择一个1*2(1行2列，不能2行1列)的区域，将所有字符都变成1。游想知道，将所有字符都变成1需要最少操作多少次?

输入描述

第一行输入两个正警数$n,m$，用空格隔开。接下来的$n$行，每行输入一个长度为$m$的01串，代表小红拿到的矩阵

$2\le n,m\le 1000$

输出描述

一个整数，代表小红的最小操作次数

样例

输入

2 4
1010
1000

输出

4