跳转至

AOJ-0525 Osenbei（经典暴力DFS，剪枝加速）

原文为日文，采用Google翻译

Description

自成立以来，IOI糖果就使用传统食谱烤制米饼。在这种传统方法中，将正面用木炭烘烤一定时间，然后在烘烤正面时翻过来，然后用木炭将背面烘烤一定时间。在保持这一传统的同时，用机器烤米饼。本机将米饼烘烤成R行（1≤R≤10）行和C列（1≤C≤10000）行的矩形排列。通常，当正面被烧时，米饼同时被翻转，背面被烘烤。

一天，在烘烤薄脆饼干的过程中，刚好在翻脆薄脆饼干之前发生了地震，还翻了几只薄脆饼干。幸运的是，木炭燃烧的条件仍然合适，但是，如果再对正面进行烘烤，则将超过自其成立以来传统所规定的烘烤时间，并且米饼的正面会变得太热而无法作为产品运输。因此，他迅速将机器更改为手动操作，并试图只交还未交接的米果饼干。该机器可以同时翻转几行或同时翻转几列，但不幸的是，它不能一次翻转一个糯米饼。

如果需要时间将其翻转，那么由于地震未翻转的糯米饼的正面将变得太热而无法作为产品运输，因此一些水平行将同时翻转一次，然后一些垂直行将同时翻转一次。因此，我们决定在不过度烘烤正面的情况下增加可以在两侧烘烤的仙贝的数量，即可以运送的仙贝的数量。考虑以下情况：没有水平行被翻转，或者没有垂直列被翻转。编写一个程序，输出可以运输的最大数量的米果饼干。

地震发生后，糯米饼立即处于下图所示的状态。黑色圆圈表示正面在燃烧，白色圆圈表示背面在燃烧。

img

如果翻转第一行，将看到下图。

img

另外，如果翻转第一和第五列，您将看到下图。在这种状态下，可以运送9个大米饼干。

img

Hint

请注意，R的上限10, C的上限10000。

Input

输入包含多个数据集。每个数据集都以以下格式给出。

输入的第一行包含两个由空格隔开的整数R和C（1≤R≤10，1≤C≤10000）。接下来的R行显示了地震后立即爆米花的状态。在第（i +1）行（1≤i≤R）中，C个整数ai，1，ai，2，……，ai，C隔开一个空格，ai，j为i它在第j列和第j列中表示饼干的状态，如果ai，j为1，则烘焙正面，如果为0，则烘焙背面。

当C和R均为0时，表示输入结束，数据集数不超过5。

Output

对于每个数据集，可以在一行上输出可以运输的大米饼干的最大数量。

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

（做AOJ和ALGOSPOT的题目真心费事，每次都需要翻译……）

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int m = 10, n = 10000;
int res = 0;
vector<vector<int> > ground(m, vector<int>(n));

//参数x代表搜索到第x行
void DFS(int x)
{
    //到了最后一行了，开始对列进行变动
    if (x == m) {
        //如果矩阵里全是0，无需进行处理
        if (res == m * n) return;
        //对每一列，如果1的个数大于0的个数则翻转
        int zeroSum = 0;
        for (int i = 0; i < n; ++i) {
            int oneNum = 0; //每一列1的个数
            for (int j = 0; j < m; ++j) {
                //位运算加速，每一行只能是0或1，可以用判断奇偶数的方法
                if (ground[j][i] & 1) ++oneNum;
            }
            zeroSum += max(oneNum, m - oneNum);
        }
        res = max(zeroSum, res);
        return;
    }

    //对第x行不翻转的搜索
    DFS(x + 1);
    //对第x行进行翻转
    for (int i = 0; i < n; ++i) ground[x][i] = !ground[x][i];
    //对第x行翻转后进行搜索
    DFS(x + 1);
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while ((cin >> m >> n) && m && n) {
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                cin >> ground[i][j];
            }
        }
        DFS(0);
        cout << res << endl;
        res = 0;
    }

    return 0;
}

这道题目其实看注释基本上就能理解程序的思路了。这道题可以很好的练习DFS的基本思路，因为行数较少，考虑每一行翻转和不翻转两种情况，则只需要分析2^{10}也就是1024种情形，对于列则最优翻转策略是这一行如果1的数目多则翻转，否则不翻转，因为只希望求得最终结果，所以分析列的时候没必要真的翻转，中间有一个利用位运算进行加速的点。另外考虑剪枝，因为如果出现可以让矩阵里的所有数都变成0，那么后面无论怎么分析都不会改变最终结果了，所以在考虑DFS终止的时候增加了一个判断。

这个题目其实也启发了对类似黑白棋的思路，试想如果这道题目变成：是否存在翻转方案，让所有的数字都变成0.那么完全可以对本题的程序稍加改动。仍然求出最终结果res，但是需要增加一个bool flag = false;，当res == m * n;的时候令flag = true;。