Osenbei AOJ 0525 DFS 穷竭搜索

题目大意是讲一个烧饼铺，在一个n * m (1<=n<=10,1<=m<=10000)的烤桌上面摆着一堆烧饼，数字1表示烧饼正面，0表示烧饼反面。然后你每次可以将一整行或者一整列的烧饼翻面，即正面翻成反面或者反面翻成正面。但是必须是一整列或者一整行的翻，问最多可以使都少烧饼翻成正面？
Sample input
2 5
0 1 0 1 0
1 0 0 0 1
3 6
1 0 0 0 1 0
1 1 1 0 1 0
1 0 1 1 0 1
0 0
Sample output
9
15

解题思路:
由于n比较小，所以可以对行DFS，模拟对行的所有操作。
那列呢？其实列很好处理，对每一列统计1的个数或者0的个数，保留最大者即是最大的正面个数: 试想如果当前列正面个数多，那这一列就不翻面; 如果反面多，那么将该列翻面即可使得原先反面变成正面，所以对列直接统计即可。
这题需要注意的是无论哪一行或者哪一列先翻面不影响结果，即翻面的顺序不影响结果，只考虑该行或该列是否要翻面即可，所以可以直接DFS。

AC代码

#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
char map[11][10001];
int ans;//保存结果void change(int a) {
    //翻面函数for (int i = 0; i < m; i++) {
    if (map[a][i] == '1') {
     map[a][i] = '0'; }else {
    map[a][i] = '1';}}
}
void DFS(int a) {
    //a代表第几行(0 ~ n-1)if (a == n) {
    //列举到最后再统计int tmp = 0;for (int j = 0; j < m; j++) {
    int tmple = 0;for (int i = 0; i < n; i++) {
    if (map[i][j] == '1') tmple++;}tmp += max(tmple, n - tmple);}ans = max(ans, tmp);return;}DFS(a + 1);change(a);DFS(a + 1);return;
}
int main() {
    while (cin >> n >> m) {
    if (n == 0 && m == 0) {
     break; }for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
    cin >> map[i][j];}}ans = 0;DFS(0);cout << ans << endl;}
}