425B


  Posted on 12 Dec 2014
greedy enumeration

Description


A matrix with rows and columns consists of 1s and 0s. () We are asked to change the matrix with less than operations. () After the change, every connected region is a rectangle. Output the minimal number of operations needed.

Tutorial


The final matrix must look like a chess board but with rectangles of 1s and 0s instead of squares of black and white. So there is a vector has values can serve as a pattern of each column. Every column either the same as or different with in every value. If we found , we can easily use greedy to decide how many operations we need to change each column into or its counter part.

Posit . There are two situations. The first is , which means some columns cannot be modified, since (because and ). If we modify each column, we must use more than operations which is not allowed. So we just enumerate each column as and calculate the answer.

The second situation is . Since , we can just enumerate all the possible with , and use the same method to calculate the answer.

Solution


#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 110;
const int MAX_M = 110;

int n, m, opr_num;
int f[MAX_N][MAX_M];
int vec[MAX_N];

void make(int bits)
{
	int i = 0;
	while (bits)
	{
		vec[i++] = bits & 1;
		bits >>= 1;
	}
}

int work()
{
	int ret = 0;
	for (int i = 0; i < m; i++)
	{
		int same = 0;
		int diff = 0;
		for (int j = 0; j < n; j++)
		{
			if (vec[j] == f[j][i])
			{
				same++;
			}else
			{
				diff++;
			}
		}
		ret += min(same, diff);
	}
	return ret;
}

int main()
{
	//input
	scanf("%d%d%d", &n, &m, &opr_num);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (m > n)
			{
				scanf("%d", &f[i][j]);
			}else
			{
				scanf("%d", &f[j][i]);
			}
		}
	}
	if (n > m)
	{
		swap(m, n);
	}

	//work
	int ans = n * m;
	if (n <= opr_num)
	{
		for (int i = 0; i < (1 << n); i++)
		{
			make(i);
			ans = min(ans, work());
		}
	}else
	{
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				vec[j] = f[j][i];
			}
			ans = min(ans, work());
		}
	}
	if (ans > opr_num)
	{
		puts("-1");
	}else
	{
		printf("%d\n", ans);
	}
	return 0;
}