Codeforces 425B

点击打开题目链接　

题意：给定一个ｎ×ｍ的０，１矩阵，做多可以对矩阵做ｋ次变换，每次变换只可以将矩阵的某一个元素由０变成１，或从１变成０。

求最小的变换次数使得得到的矩阵满足：每一个连通块都是一个“实心”矩形。

要想清楚的就是最终的矩阵一定是这样的：　

0１０...

1 0 1 ...

0 1 0 ...　这样的０，１交替的矩阵，这里０，１分别表示一个矩形。

如果　n > k，　那么肯定又一行是没有改变的（为什么？想一想），那么只需要枚举这没有改变的一行，其他行要么和他完全相同，要么完全不同（为什么？想一想）。并且任何两行之间没有任何的其他依赖关系，所以只需要取变换次数最少的一种。

如果　ｎ< k, 　那么可以枚举第一列最后的情况，也就是２^ n，这里ｎ< k,　而且ｋ<10。　然后和上面一样就可以了。

附上代码：

 1 /*************************************************************************
 2     > File Name: 425B.cpp
 3     > Author: Stomach_ache
 4     > Mail: sudaweitong@gmail.com
 5     > Created Time: 2014年04月30日 星期三 21时44分14秒
 6     > Propose: 
 7  ************************************************************************/
 8 
 9 #include <cmath>
10 #include <string>
11 #include <cstdio>
12 #include <fstream>
13 #include <cstring>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 
18 #define MAX_N (100 + 5)
19 #define min(x, y) ((x) < (y) ? (x) : (y))
20 
21 int n, m, k;
22 int a[MAX_N][MAX_N];
23 
24 int
25 main(void) {
26         scanf("%d %d %d", &n, &m, &k);
27         for (int i = 0; i < n; i++) 
28                 for (int j = 0; j < m; j++) 
29                         scanf("%d", &a[i][j]);
30         int ans = 10005;
31         if (k < n) {
32                 for (int i = 0; i < n; i++) {
33                         int tmp = 0;
34                         for (int j = 0; j < n; j++) if (i != j) {
35                                 int cnt1 = 0, cnt2 = 0;
36                                 for (int t = 0; t < m; t++) {
37                                         if (a[j][t] == a[i][t]) {
38                                                 cnt1++;
39                                         } else {
40                                                 cnt2++;
41                                         }
42                                 }
43                                 tmp += min(cnt1, cnt2);
44                         }
45                         if (tmp < ans) {
46                                 ans = tmp;
47                         }
48                 }
49         } else {
50                 for (int i = 0; i < (1<<n); i++) {
51                         int tmp = 0, b[MAX_N];
52                         for (int j = 0; j < n; j++) {
53                                 if (i & (1<<j)) {
54                                         if (a[j][0] == 0) {
55                                                 b[j] = 1;
56                                                 tmp++;
57                                         } else {
58                                                 b[j] = 1;
59                                         }
60                                 } else {
61                                         if (a[j][0] == 1) {
62                                                 b[j] = 0;
63                                                 tmp++;
64                                         } else {
65                                                 b[j] = 0;
66                                         }
67                                 }
68                         }
69                         for (int j = 1; j < m; j++) {
70                                 int cnt1 = 0, cnt2 = 0;
71                                 for (int t = 0; t < n; t++) {
72                                         if (a[t][j] == b[t]) {
73                                                 cnt1++;
74                                         } else {
75                                                 cnt2++;
76                                         }
77                                 }
78                                 tmp += min(cnt1, cnt2);
79                         }
80                         if (tmp < ans) {
81                                 ans = tmp;
82                         }
83                 }
84         }
85         if (ans > k) {
86                 puts("-1");
87         } else {
88                 printf("%d
", ans);
89         }
90         
91         return 0;
92 }