题目描述:

对于给出的一个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 } 
01-08 05:25