题目描述：

输入H，W，n，m，T，和H*W的01矩阵。

让你在H*W的矩阵中找到n*m个边长为a的小正方形，相邻正方形之间的距离为b，正方形和边界的距离也是b。并且a>=b。如图：
http://s8/middle/64675f54gaec0422e9457&6903548 2分匹配 Chess Board" TITLE="ZOJ 3548 2分匹配 Chess Board" />

你可以进行如下操作：把任意一个矩形涂成黑色或者白色，花费时间为T。

问你最少花费多少时间能够涂成满足上述条件的形式。

解题报告：

         首先，把H*W的图分成如下几种颜色的块：
        http://s10/middle/64675f54gaec043d53339&6903548 2分匹配 Chess Board" TITLE="ZOJ 3548 2分匹配 Chess Board" />

枚举a和b，对于满足n * (a + b) + b == h && m * (a + b) + b == w的a和b，我们一定能够涂成目标形式。设一共要涂ans个矩形。

1         扫描n*m个应该是白色的块，这些块一定要单独涂色，对于每个块，如果这个块中有一点黑色，ans++，然后扫描下一个。

2         设mat[n+1][m+1]为n+1*m+1个b*b的小块（图中红色的块），如果i行j列的块中有一个白点，就把mat[i][j]标记为1，否则为0.

3         扫描图中所有绿色的长方块，如果第i行有一个绿色的块中有白点，那么就把这一行都涂成黑色，ans++，同时把在这一行的mat[i][所有]都标记为0，表示没有白点。

4         同理，扫描图中所有灰色的长方块，如果第j列有一个灰色的块中有白点，那么就把这一列都涂成黑色，ans++，同时把在这一列的mat [所有] [j]都标记为0，表示没有白点。

5         不难证明，1，3,4步的涂法是必须的（应为每个块不能重复涂不同的颜色），那么，此时剩下的就是红色块了（mat[i][j]=1）的，此时问题转化成：

一次可以干掉一行的或者一列的，问最少多少次可以干完。

相信到了这里大家就明白了，二分匹配最小点覆盖求解之。

代码如下：

#include<iostream>

#include<cstring>

#include<vector>

#include<algorithm>

#include<cmath>

#include<cstdio>

using namespace std;

int h, w, n, m, t;

char str[2010][2010];

int match[300], vst[300];

int mat[300][300];

vector<int> g[300];

int find(int id)

{

    for(int i = 0; i < g[id].size(); i++) if (!vst[g[id][i]])

    {

        vst[g[id][i]] = true;

        if (match[g[id][i]] == -1 || find(match[g[id][i]]))

        {

            match[g[id][i]] = id;

            return 1;

        }

    }

    return 0;

}

int solve(int n)

{

    memset(match, -1, sizeof(match));

    int tar = 0;

    for(int i = 0; i < n; i++)

    {

        memset(vst, 0, sizeof(vst));

        tar += find(i);

    }

    return tar;

}

int main()

{

    while(scanf("%d%d%d%d%d", &h, &w, &n, &m, &t) != EOF)

    {

        for(int i = 0; i < h; i++) scanf("%s", str[i]);

        int ans = -1;

        for(int a = min(h / n, w / m); a >= 1; a--)

            for(int b = a; b >= 1; b--) if (n * (a + b) + b == h && m * (a + b) + b == w)

            {

                int tmpans = 0;

                for(int i = 0; i < n; i++) for(int j = 0; j < m; j++)

                {

                    bool flag = false;

                    for(int i2 = i * (a + b) + b; i2 < (i + 1) * (a + b); i2++)

                        for(int j2 = j * (a + b) + b; j2 < (j + 1) * (a + b); j2++)

                            if (str[i2][j2] == '0'){flag = true;goto lable;}

                    lable:

                    if (flag) tmpans++;

                }

                int l = n + 1, r = m + 1;

                memset(mat, 0, sizeof(mat));

                for(int i = 0; i < l; i++) for(int j = 0; j < r; j++)

                {

                    bool flag = false;

                    for(int i2 = i * (a + b); i2 < i * (a + b) + b; i2++)

                        for(int j2 = j * (a + b); j2 < j * (a + b) + b; j2++)

                            if (str[i2][j2] == '1')

                            {flag = true; goto lable2;}

                    lable2:

                    if (flag) mat[i][j] = 1;

                }

                for(int i = 0; i < l; i++) for(int j = 0; j < m; j++)

                {

                    bool flag = false;

                    for(int i2 = i * (a + b); i2 < (i + 1) * b + i * a; i2++)

                        for(int j2 = (j + 1) * b + j * a; j2 < (j + 1) * (a + b); j2++)

                            if (str[i2][j2] == '1')

                            {flag = true; goto lable3;}

                    lable3:

                    if (flag)

                    {

                        for(int i2 = 0; i2 < r; i2++) mat[i][i2] = 0;

                        tmpans++;

                        break;

                    }

                }

                for(int j = 0; j < r; j++) for(int i = 0; i < n; i++)

                {

                    bool flag = false;

                    for(int i2 = i * (a + b) + b; i2 < (i + 1) * (a + b); i2++)

                        for(int j2 = j * (a + b); j2 < j * (a + b) + b; j2++)

                            if (str[i2][j2] == '1')

                            {flag = true; goto lable4;}

                    lable4:

                    if (flag)

                    {

                        for(int i2 = 0; i2 < l; i2++) mat[i2][j] = 0;

                        tmpans++;

                        break;

                    }

                }

                for(int i = 0; i < l; i++)

                {

                    g[i].clear();

                    for(int j = 0; j < r; j++) if (mat[i][j])

                        g[i].push_back(j);

                }

                tmpans += solve(l);

 

                if (ans == -1 || tmpans < ans) ans = tmpans;

            }

        ans *= t;

        printf("%d\n", ans);

 

    }

         return 0;

}