模拟题,根据题意进行贪心模拟即可。 我们需要将所有非 1 的字符全部修改为 1 ,所以一旦遇到一个为 1 的字符,就将其修改为 1 ,并将其相邻的字符也一并修改为 1。 这里我们考虑将当前字符以及其右边的字符修改为 1 的贪心方式,这样遍历的同时进行修改,使得最终需要进行修改的字符数量最少即可。 时间复杂度:O(nm)
n, m = map(int, input().split())
小红拿到了一个01矩阵,她每次操作可以选择一个1*2(1行2列,不能2行1列)的区域,将所有字符都变成1。游想知道,将所有字符都变成1需要最少操作多少次?
第一行输入两个正警数n,m,用空格隔开。接下来的n行,每行输入一个长度为m的01串,代表小红拿到的矩阵
2≤n,m≤1000
一个整数,代表小红的最小操作次数
输入
2 4
1010
1000
输出
4