時間制限:1000ミリ秒
メモリ制限:65536KB
問題
Annoying painting tool
貴方は使い勝手の悪いペイントツールを知っているだろうか?
それは次のようなペイントツールである。
このペイントツールはピクセル形式で色は白か黒(0か1)しか扱わない。
そしてこのツールは、r,c(rは高さcは横幅でサイズは固定されている)サイズの矩形範囲を画像の中で選択できその範囲の色を変更する操作が可能である。
この操作では選択された範囲のマスのうち、白色のマスは黒色に、黒色のマスは白色に変更される。
これを操作Bと定義する。
- 入力はn行m列の画像データAと,選択可能な矩形範囲の形r行c列の選択範囲が与えられる。
最初画像は全て白(0)から初めて、何回か操作Bを繰り返してAの画像を作れた時。
画像Aを作るための操作Bの最小回数を求めてほしい。
操作Bで画像Aを作れないときは-1と出力すること。
入力は複数のデータセットが与えられる。
一つのデータセットは画像サイズを表すn、m(画像の高さと幅)、r,c(選択可能な矩形範囲の高さと幅)
続くn行には作るべき画像データ(0が白で1が黒)が一行ずつ与えられる。
h,w,r,cがともに0のとき入力の終了をあらわす。
入力の例
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
出力の例
4 6 -1
出典
Ulm Local 2007