hdu1801 01翻转 贪心

题目描述：

对于给出的一个n*m的矩形，它由1和0构成，现在给你一个r*c的矩形空间可以选择，且可以选择无数次（被选中的范围内01翻转），要求问将这个01矩阵全部变成0的最少需要翻多少次，且如果无法实现输出-1

题目分析：

对于单个位置而言，不是0就是1，且如果是1则必须接受反转，对某个点来说，反转1，3，5，7...次是一样的，翻转0，2，4，6，8...次是一样的，所以对于矩形N*M中的任何一个点只有反转和不反转两种选择，而如果是1，则必须接受反转，所以我们需要做的就是从左上开始，一行一行每个位置依次判断，（将这个点作为你反转矩阵r*c的左上角）这样能保证主动去反转的每个点只翻一次，且不会被后面的翻转情况所影响（翻前面的点时后面的下面的点可能会一同被反转，但是没有关系，我们接下来会去依次判断，我们的循环就是从上往下，从左往右）

这是一种贪心的思维，我们每次需要翻转的情况都是必须翻的，而一旦遇到需要反转，但是剩余的选择空间不足以容纳以该点为左上角的r*c的矩阵时，返回-1，翻转成功计数器+1

代码：

#include<iostream>
using namespace std;

char mat[105][105];
int n, m, r, c;

int run(){
    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(mat[i][j] == '1'){
                int row = i+r-1;
                int col = j+c-1;
                if(row <= n && col <= m){    
                    ans++;
                    for(int k = i; k <= row; k++){
                        for(int l = j; l <= col; l++){
                            if(mat[k][l] == '1') mat[k][l] = '0';
                            else mat[k][l] = '1';
                        }
                    }        
                }else{
                    return 0;
                }
            }
        }
    }        
    return ans;
}

int main(){
    while(scanf("%d%d%d%d", &n, &m, &r, &c) != EOF){
        if(n == 0) break;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                cin>>mat[i][j];
            }
        }
        int cnt = run();
        if(cnt == 0) printf("-1
");
        else printf("%d
", cnt);
    }
    return 0;
}