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

深藏阁楼爱情的钟 2021-11-02 06:32 179阅读 0赞

# 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 ith line consists of m characters describing the desired pixel values of the ith 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

010

101

010

4 3 2 1

011

110

011

110

3 4 2 2

0110

0111

0000

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

转载于:https://www.cnblogs.com/lidaojian/archive/2012/03/11/2390283.html