2007/2008 ACM International Collegiate Programming Contest
University of Ulm Local Contest

Problem A: Annoying painting tool

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 Specification

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 Specification

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

4
6
-1

---

題目給定一個矩形，然後一次操作可以將固定的小矩形內部的0/1反轉。
求最少的操作次數。

一開始很容易以為是最少費用流之類的處理，但隨後地會發現，
反轉的一次區域都是固定的小矩形，不會受到特別的方式去干擾，
因此先滿足左上角的點，依序將所有點反轉。

如果途中超過邊界，即無法翻轉成功則輸出 -1。

#include <stdio.h>

int main() {
    int n, m, r, c;
    char g[105][105];
    while(scanf("%d %d %d %d", &n, &m, &r, &c) == 4) {
        if(n+m+r+c == 0)
            break;
        int i, j, p, q;
        for(i = 0; i < n; i++)
            scanf("%s", g[i]);
        int ret = 0;
        for(i = 0; i < n; i++) {
            for(j = 0; j < m; j++) {
                if(g[i][j] == '0')  continue;
                if(i+r-1 >= n || j+c-1 >= m) {
                    ret = -1;
                    j = m, i = n;
                    continue;
                }
                ret++;
                for(p = 0; p < r; p++) {
                    for(q = 0; q < c; q++) {
                        if(g[i+p][j+q] == '1')
                            g[i+p][j+q] = '0';
                        else
                            g[i+p][j+q] = '1';
                    }
                }
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}