HDU 1801 || SDUT 2372 Annoying painting tool（贪心）

Annoying painting tool

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 234 Accepted Submission(s): 167

Problem Description

Maybe you wonder what an annoying painting tool is? First of all, the painting tool we speak of supports only black and white. Therefore, a picture consists of a rectangular area of pixels, which are either black or white. Second, there is only one operation how to change the colour of pixels:

Select a rectangular area of r rows and c columns of pixels, which is completely inside the picture. As a result of the operation, each pixel inside the selected rectangle changes its colour (from black to white, or from white to black).

Initially, all pixels are white. To create a picture, the operation described above can be applied several times. Can you paint a certain picture which you have in mind?

Input

The input contains several test cases. Each test case starts with one line containing four integers n, m, r and c. (1 ≤ r ≤ n ≤ 100, 1 ≤ c ≤ m ≤ 100), The following n lines each describe one row of pixels of the painting you want to create. The i^th line consists of m characters describing the desired pixel values of the i^th row in the finished painting ('0' indicates white, '1' indicates black).
The last test case is followed by a line containing four zeros.

Output

For each test case, print the minimum number of operations needed to create the painting, or -1 if it is impossible.

Sample Input

3 3 1 1

4 3 2 1

3 4 2 2

0 0 0 0

Sample Output

-1

Source

2007~2008 University of Ulm Local Contest

解题报告：这是昨天内部比赛的题，当时分配任务的时候，我看前三个题，这个题是第一个，看完题目时感觉像是搜索题，但是没有想出具体办法，哎！比赛的时候没有做出来，今天搜的解题报告，原来是利用贪心，就是自左向右，自上而下遍历一次，若遇见和所给的不同就变换（可变化的区域），最后再和所给的比较即可！

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 110;
int map[N][N], colour[N][N];
char str[N][N];
int n, m, r, c, ans;
void Change()
{
    int i, j, k, p;
    for (i = 0; i < n; ++i)//从头到尾遍历一回
    {
        for (j = 0; j < m; ++j)
        {
            if (i + r <= n && j + c <= m && map[i][j] != colour[i][j])//变化范围
            {
                for (k = i; k < i + r; ++k)
                {
                    for (p = j; p < j + c; ++p)
                    {
                        if (colour[k][p])
                        {
                            colour[k][p] = 0;
                        }
                        else
                        {
                            colour[k][p] = 1;
                        }
                    }
                }
                ans ++;//变化的次数
            }
        }
    }
}
int Judge()//判断是否和所给的相同
{
    int i, j;
    for (i = 0; i < n; ++i)
    {
        for (j = 0; j < m; ++j)
        {
            if (map[i][j] != colour[i][j])
            {
                return 0;
            }
        }
    }
    return 1;
}
int main()
{
    int i, j;
    while (scanf("%d%d%d%d", &n, &m, &r, &c) != EOF && n && m && r && c)
    {
        ans = 0;
        memset(colour, 0, sizeof(colour));
        memset(map, 0, sizeof(map));
        memset(str, 0, sizeof(str));
        getchar();//度掉回车
        for(i = 0; i < n; ++i)
        {
            scanf("%s", str[i]);
            for (j = 0; j < m; ++j)
            {
                map[i][j] = str[i][j] - '0';
            }
        }
        Change();//变化函数从左上角开始比较
        if (Judge())
        {
            printf("%d\n", ans);
        }
        else
        {
            printf("-1\n");
        }
    }
    return 0;
}