CODEWITHSUNDEEP
algorithmmatrixgreedy
user3070752
user3070752

Reputation:

A greedy algorithm for converting a binary matrix to zero matrix by flipping the cells

We have a M*N matrix with some 1 and 0, we want to make all of these cells zero using a 2*2 square. When this square is pushed on 4 cells their contents will be flopped. We want to find if there is any answer to a given matrix to completely convert all cells to zero or not.

Is there any greedy answer to this?

Upvotes: 1

Views: 374

Answers (1)

Rafael Baptista
Rafael Baptista

Reputation: 11499

Call your larger matrix M and your small one ( the 2x2 ) P

Scan your P from left to right, and top to bottom on M. Every time the top left hand of cell of P on M is 1 apply P.

By the time you get to the bottom right part of M every cell except the right hand column and bottom row of M is guaranteed to be 0.

If those last columns are not zero then there is no solution.

You can prove that not every matrix can be cleared by this process. For example if M were a 2x2 non-zero matrix it could never be cleared using this process.

Neither can any matrix M of any size with between 1 and 3 cells set to 1.

I suspect that there is a more general unsolvable case - e.g. it could be that matrices that don't have a multiple of 4 bits set to 1 cannot be solved this way.

Thinking about it more - I don't think you can solve any matrix with an odd number of 1's on any row or column.

Upvotes: 1

Related Questions