## 425B

Posted on 12 Dec 2014
greedy enumeration

### Description

A matrix with $n$ rows and $m$ columns consists of 1s and 0s. ($1\leq n,m \leq 100$) We are asked to change the matrix with less than $k$ operations. ($1\leq k \leq 10$) 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 $x$ has $n$ values can serve as a pattern of each column. Every column either the same as $x$ or different with $x$ in every value. If we found $x$, we can easily use greedy to decide how many operations we need to change each column into $x$ or its counter part.

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

The second situation is $n \leq k$. Since $k \leq 10$, we can just enumerate all the possible $x$ with $O(2^n)$, 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;
}