P3363. 恼人的绘画工具

ID: 2364
远端评测题
1000ms
64MiB
尝试: 0
已通过: 0
难度: (无)
上传者:

Hydro
标签:

题目描述

你是否好奇什么是“恼人的绘画工具”？首先，我们所说的绘画工具仅支持黑白两色。因此，一幅图像由一个矩形像素区域组成，每个像素要么是黑色，要么是白色。其次，改变像素颜色的操作只有一种：

选择一个完全包含在图像内的 r 行 c 列的矩形区域。操作执行后，所选矩形内的每个像素都会翻转颜色（黑色变白色，白色变黑色）。

初始时，所有像素均为白色。若要通过多次应用上述操作创作出一幅目标图像，请问是否可行？若可行，输出所需的最小操作次数；否则输出 -1。

输入格式

输入包含多个测试用例。每个测试用例的第一行包含四个整数 n, m, r, c（1 ≤ r ≤ n ≤ 100，1 ≤ c ≤ m ≤ 100）。接下来的 n 行每行描述目标图像的一行像素，其中第 i 行包含 m 个字符，表示完成后第 i 行的像素值（'0' 表示白色，'1' 表示黑色）。

最后一个测试用例之后是一行四个零。

输出格式

对每个测试用例，输出创建目标图像所需的最小操作次数；若无法实现，输出 -1。

输入数据示例 1

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  

输出数据示例 1

4  
6  
-1  

来源

乌尔姆本地赛 2007