Volume 5 / 0525

情報オリンピック 2007予選 解答

Problem 0525 : Osenbei

公式の解説のまんま。

#include <iostream>
#include <vector>

using namespace std;


// 数え上げ
int countUp( vector< vector<int> > src )
{
	int i, j, cnt, result = 0;


	for( j=0; j<src[0].size(); j++ ){
		cnt = 0;
		for( i=0; i<src.size(); i++ )
			if( src[i][j] ) cnt++;
		result += ( cnt > src.size()-cnt ) ? cnt : src.size()-cnt;
	}

	return result;
}

// ひっくり返す行の組み合わせを全て試す
int solve( vector< vector<int> > src, int x )
{
	int max, new_val, i;

	for( i=0; i<src[x].size(); i++ )
		src[x][i] = (src[x][i]+1)%2;

	max = countUp( src );

	for( i=x+1; i<src.size(); i++ ){
		new_val = solve( src, i );
		if( max < new_val )
			max = new_val;
	}

	return max;
}

int main(void)
{
	int r, c, input, i, j, max, new_val;
	vector< vector<int> > senbei;

	while( cin >> r >> c, r != 0 ){
		senbei.clear();

		senbei.resize(r);
		for( i=0; i<r; i++ ){
			for( j=0; j<c; j++ ){
				cin >> input;
				senbei[i].push_back(input);
			}
		}

		max = countUp(senbei);
		for( i=0; i<senbei.size(); i++ ){
			new_val = solve( senbei, i );
			if( max < new_val )
				max = new_val;
		}

		cout << max << endl;

	}

	return 0;
}