Coin flipping game: Optimization problem

[Arpit Tarang]

This came in a competition:
There is a rectangular grid of coins, with heads being represented by the value 1 and tails being represented by the value 0. You represent this using a 2D integer array table (between 1 to 10 rows/columns, inclusive).

In each move, you choose any single cell (R, C) in the grid (R-th row, C-th column) and flip the coins in all cells (r, c), where r is between 0 and R, inclusive, and c is between 0 and C, inclusive. Flipping a coin means inverting the value of a cell from zero to one or one to zero.

Return the minimum number of moves required to change all the cells in the grid to tails. This will always be possible.

Examples:
1111
1111
returns: 1

01
01
returns: 2

010101011010000 101010101
returns: 20

000
000
001
011
returns: 6

How to go about this? A purely recursive algorithm would take ages... How can constraints be applied to reduce recursive calls? Or is there a better method? Thanks in advance.

[whodgson]

Or is there a better method?

Which method are you referring to? there is no code posted.

[Arpit Tarang]

I meant this:
Since the order of flipping doesn't matter, and making a move on a coin twice is like not making a move at all, we can just find all distinct combinations of flipping coins, and minimizing the size of good combinations(go od meaning those that give all tails).

This can be done by making a set consisting of all coins, each represented by an index.(i.e. if there were 20 coins in all, this set would contain 20 elements, giving them an index 1 to 20). Then make all possible subsets and see which of them give the answer(i.e. if making a move on the coins in the subset gives us all tails). Finally, minimize size of the good combinations.

I don't know if I've been able to express myself too clearly... I'll post a code if you want.

[mohitkhurana102]

is this always possible that all the cells of any grid can be changed into tails? explain

[Arpit Tarang]

Well it was given in the question that it is always possible..