[UVA] 11230 - Annoying painting tool
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 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 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;
}