I was trying to solve http://www.codechef.com/ACMAMR12/problems/LIGHTS yesterday. Accidentally, I read the question wrong. Instead of doing flips on rows only, I did it for for row and column. Obviously my approach was wrong and after looking at others solutions, I found my mistake. Now I wonder, what if the question had said what I previously thought. What if flips are allowed not only in rows but also in columns.

e.g. k=2

- . * *

. * . .

- . * *

flipping row 2 and column 2, we will get maximum *.

I am unable to find an approach for this. I think it will be a dp problem. Still, how to solve it? Any pointers would be helpful.