2013年7月7日 星期日

11230 - Annoying painting tool

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

Problem A: Annoying painting tool

或許你不知道這一個很惱人的繪圖工具。首先 ,它只支援黑白兩種顏色,畫面中只有一個矩形的像素區域。接著只會有一種顏色改變的操作。

選擇一個 r 行(row) x c 列(column) 的區域,接著在內部的所有像素反轉,在這個操作後,原本的黑色會變白色,或者白色轉換成黑色。

一開始所有像素都是白色。創建一張圖,最少要幾次的操作才能繪出心中想的那張圖。

Input Specification

輸入有數筆,每組測資地一行將會有四個整數 n, m, r and c. (1 ≤ r ≤ n ≤ 100, 1 ≤ c ≤ m ≤ 100) 接著會有 n 行,每行上會有 m 個像素。以表示最後要完成的圖形 (以 '0' 表示白色, '1' 表示黑色)。


最後一筆測資將會包含四個 0,結束程序。

Output Specification

對於每組測資輸出最少的操作次數,如果無法轉換,則輸出 "-1" 。

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