POJ 1222 : EXTENDED LIGHTS OUT

問題

縦5×横6の配列が与えられる。配列の要素は1か0である。与えられた配列の要素を全て0にする。ただし、注目点と四近傍は同時に反転される。

解法

貪欲法で解ける。ひとつ上の要素が1ならその注目点で反転させる。一番上の要素の状態を全探索し、全て0にでたらそれが答えになる。
30bitあるので、全ての要素に対して探索をするとTLEになりそう。

計算量

X:横の要素数
Y:縦の要素数

コード