425B

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;
}