Daily programming #0051

DailyProgramming Python3

競技プログラミングの問題をやる機会があったのでPOJ No.3279(Fliptile)をやっていく。

POJ No.3279(Fliptile)[Python]

Question

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

Input

1行目はスペースで区切られた2つの整数N、M。
2行目からM+1行目は、N個のスペースで区切られた0か1の整数。
整数は1は黒、0は白のマスを表す。

Output

すべてのマスを白色にするまでに、特定の位置を何回ひっくり返すかをM x Nのマトリクスで表示する。 ただし、解が存在しない場合は、"IMPOSSIBLE"と出力する。

Sample Input

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

Sample Output

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

Code

POJ No.3279(Fliptile)

Output

$ python < input.txt
0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0

glot.ioでは上記以外の場合のサンプルも結果として出力するようにした。

Comment

この問題は競技プログラミングの教本プログラミングコンテストチャレンジブック、俗に言う蟻本の中に同じ問題が入っています。私はこの本を持っていますが、どうやらGoogle Booksでも参照できるようです。

蟻本は、かなり前に一読しましたがPythonでは試したことがなかったので今回この問題をやってみました。
が、ほぼ蟻本の内容をPythonに落とし込んだだけの形になってしまった・・・
特に全パターンをビットシフトで出すなどは、頭では理解できても慣れていないとすぐにはでてこなかったです。
暇があったら他の問題にもチャレンジしてみたいと思います。