3279 Fliptile

原文

時間制限:2000ミリ秒
メモリ制限:65530KB

問題

農家ジョンは賢い牛ほどよくミルクを出すことを知りました。そこで、牛たちを賢くするために次のようなゲームを用意しました。M×N (1 ≤ M ≤ 15; 1 ≤ N ≤ 15)のマス目があり、各マスごとに裏表をひっくり返すことが可能で、一方の面は黒色、他方は白で塗られています。ゲームの目的はすべてのマスを白色にすることです。ところが牛の蹄は大きいため、一マスひっくり返そうとすると、その縦横に隣接するマスごとひっくり返してしまいます。ひっくり返すのは疲れるので、牛たちはできるだけ少ない回数ですべてのマスを白色にしようと考えました。最小手数で各マスをひっくり返す方法を求めなさい。最小手数の解が複数ある場合は辞書順で最小のものを出力してください。解が存在しない場合はIMPOSSIBLEと出力してください。

入力

一行目はスペースで区切られた整数M、Nが与えられます。
二行目からはM行N列の整数列(黒は1、白は0)が与えられます。

出力

M×Nの反転させる位置を1,反転させない場所を0としたM行N列の盤面を出力してください。

入力の例

4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1

出力の例

0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0

出典

POJ