题目描述

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

思路

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

代码

python

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