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

代码：

 1 #include<iostream>
 2 using namespace std;
 3
 4 char mat[105][105];
 5 int n, m, r, c;
 6
 7 int run(){
 8     int ans = 0;
 9     for(int i = 1; i <= n; i++){
10         for(int j = 1; j <= m; j++){
11             if(mat[i][j] == '1'){
12                 int row = i+r-1;
13                 int col = j+c-1;
14                 if(row <= n && col <= m){
15                     ans++;
16                     for(int k = i; k <= row; k++){
17                         for(int l = j; l <= col; l++){
18                             if(mat[k][l] == '1') mat[k][l] = '0';
19                             else mat[k][l] = '1';
20                         }
21                     }
22                 }else{
23                     return 0;
24                 }
25             }
26         }
27     }
28     return ans;
29 }
30
31 int main(){
32     while(scanf("%d%d%d%d", &n, &m, &r, &c) != EOF){
33         if(n == 0) break;
34         for(int i = 1; i <= n; i++){
35             for(int j = 1; j <= m; j++){
36                 cin>>mat[i][j];
37             }
38         }
39         int cnt = run();
40         if(cnt == 0) printf("-1\n");
41         else printf("%d\n", cnt);
42     }
43     return 0;
44 }